LintCode: Rotate String-阿里云开发者社区

LintCode: Rotate String

2017-11-14 958

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

C++,

time: O(n)

space:O(n)

 1 class Solution {
 2 public:
 3     /**
 4      * @param str: a string
 5      * @param offset: an integer
 6      * @return: nothing
 7      */
 8     void rotateString(string &str, int offset) {
 9         // wirte your code here
10         // empty string->return
11         if ("" == str) {
12             return;
13         }
14         // offset is 0, return
15         int size = str.size();
16         offset = offset%size;
17         if (0 == offset) {
18             return;
19         }
20         // tmp = str+str->substr
21         string tmp(str);
22         tmp.reserve(size<<1);
23         tmp.insert(tmp.end(), str.begin(), str.end());
24         str = tmp.substr(size-offset, size);
25     }
26 };

C++,

time:O(n)

space:O(1)

 1 class Solution {
 2 public:
 3     /**
 4      * @param str: a string
 5      * @param offset: an integer
 6      * @return: nothing
 7      */
 8     void rotateString(string &str, int offset) {
 9         // wirte your code here
10         // empty string->return
11         if ("" == str) {
12             return;
13         }
14         // offset is 0, return
15         int size = str.size();
16         offset = offset%size;
17         if (0 == offset) {
18             return;
19         }
20         // 3-steps reverse
21         reverse(str, 0, size-offset-1);
22         reverse(str, size-offset, size-1);
23         reverse(str, 0, size-1);
24     }
25     void reverse(string &str, int from, int to) {
26         char tmp;
27         while( from<to ) {
28             tmp = str[from];
29             str[from] = str[to];
30             str[to] = tmp;
31             from++;
32             to--;
33         }
34     } 
35 };