旋转字符串

题目

给定一个字符串和一个偏移量,根据偏移量旋转字符串(从左向右旋转)http://www.lintcode.com/zh-cn/problem/rotate-string/

分析

非常经典的一道题目,这里只说一下O(n)复杂度的算法思路。将字符串写成向量形式,str = [a1 a2 ... an],设偏移量为x(x>0 && x<n),即希望得到的结果为[ an-x+1 an-x+2 ... an a1 a2 ... an-x],算法步骤如下:

  • 先将整个字符串向量逆序,得到 str' = [an an-1 ... a2 a1]
  • 将逆序后的字符串前x项再逆序,此时str'' =[an-x+1 an-x+2 ... an a1 a2 .. an ]
  • 经过前一个步骤,前x项已经是想要的结果了,对剩下的n-x项进行逆序,就得到了最后的正确结果

代码


public class Solution {
    // 将str从start到end逆序
    void t(char[] str, int start, int end){
        char temp;
        while(start < end){
            temp = str[start];
            str[start] = str[end];
            str[end] = temp;
            start++;
            end--;
        }
    }
    /**
     * @param str: an array of char
     * @param offset: an integer
     * @return: nothing
     */
    public void rotateString(char[] str, int offset) {
        if(str.length == 0 || str.length == 1) return;
        // offset超过待查询字符串长度时,取模
        if(offset > str.length){
            offset = offset % str.length;
        }
        if(offset <= 0) return;
        t(str, 0, str.length - 1);
        t(str, 0, offset - 1);
        t(str, offset, str.length -1);
    }
}
Show Comments

Get the latest posts delivered right to your inbox.