描述

这是一篇针对初学者的题解。
知识点：字符串
难度：一星

题解

题目抽象：给定一字符串str，将str的[0...n)子串移动到[n...len)子串的后面。

方法一：使用标准库string::substr(size_type __pos, size_type __n);

string::substr(pos, n)表示截取字符串string，从pos下标开始，长度为n的子串。
比如：str = "helloworld", 那么str.substr(2,3)等于"llo"

代码：

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if (n > str.size()) return str;
        return str.substr(n) + str.substr(0, n);
    }
};

时间复杂度：O(N), N为str的长度
空间复杂度：O(N), 具体分析看下面

方法二：遍历数组

首先分析下方法一种substr()库函数的源代码，源代码出于SGIport3.3版本。
substr()的源码如下：

 basic_string substr(size_type __pos = 0, size_type __n = npos) const {
    if (__pos > size())
      _M_throw_out_of_range();
    return basic_string(_M_start + __pos, 
                        _M_start + __pos + min(__n, size() - __pos));
  }

意思就是说，如果 __n默认缺省等于npos的话，就截取从__pos到末尾的全部字符串。
其中size(), npos的源码为：

size_type size() const { return _M_finish - _M_start; }

const size_type npos 
  = (basic_string<_CharT,_Traits,_Alloc>::size_type) -1;

其中size_type为

typedef size_t size_type;

size_t 表示uint

可知substr只用了basic_string(first,last)的构造函数，源码如下：

basic_string(_InputIterator __f, _InputIterator __l,
               const allocator_type& __a = allocator_type())
    : _Base(__a)
  {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_initialize_dispatch(__f, __l, _Integral()); // 其实是调用这个函数
  }

经追溯源代码，发现_M_initialize_dispatch其实是调用如下函数：

template <class _InputIter, class _ForwardIter>
_ForwardIter 
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __false_type)
{
  _ForwardIter __cur = __result;
  __STL_TRY {
    for ( ; __first != __last; ++__first, ++__cur)
      _Construct(&*__cur, *__first); // 最终调用到这里
    return __cur;
  }
  __STL_UNWIND(_Destroy(__result, __cur));
}

最终发现，额外构造了N个大小的空间，所以空间复杂度为O(N)

所以，可以不使用库函数，自己实现一下，代码如下：

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if (n > str.size()) return str;
        string ret = "";
        for (int i=n; i<str.size(); ++i)
            ret += str[i];
        for (int i=0; i<n; ++i)
            ret += str[i];
        return ret;
    }
};

时间复杂度：O(N)
空间复杂度：O(N)