字符串刷题笔记

541.反转字符串 II

代码实现

class Solution {
    public String reverseStr(String s, int k) {
        char[] a = s.toCharArray();
	    int i = 0;
	    int j = 0;
	    char tmp;
        for (int start = 0; start < a.length; start += 2 * k) {
            i = start;
            // 保证题目要求，小于k个字符全部反转
	        j = Math.min(start + k - 1, a.length - 1);
            while (i < j) {
                tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return new String(a);
    }
}

151.翻转字符串里的单词

API选手特供版

class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        // 在每个字符串中间添加空格作为分隔符
        return String.join(" ", wordList);
    }
}

拓展——利用额外空间实现

class Solution {
    public String reverseWords(String s) {
        // 因为最终结果字符串需要不断修改，所以为了方便选择StringBuilder
        StringBuilder res = new StringBuilder();
        // 清除首尾多余空格
        String validStr = s.trim();
        // 通过空格分隔各个字符串，并输出成数组
        String[] split = validStr.split(" ");
        // 遍历数组，逆序输出到StringBuilder初始化的对象
        for (int i = split.length-1; i >= 0 ; i--) {
            if(split[i].trim().length() > 0){
                res.append(split[i]);
                // 各个字符串添加空格，注意细节，判断条件代表每次在后面加一个空格，所以倒数第一个不需要加空格了
                if(i != 0){
                    res.append(" ");
                }
            }            
        }
        return res.toString();
    }
}

剑指 Offer 58 - II. 左旋转字符串

字符串切片

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}

列表遍历拼接

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < s.length(); i++)
            res.append(s.charAt(i));
        for(int i = 0; i < n; i++)
            res.append(s.charAt(i));
        return res.toString();
    }
}

简化

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < n + s.length(); i++)
            res.append(s.charAt(i % s.length()));
        return res.toString();
    }
}

当然字符串String类同样可以实现，只是影响性能，看面试官要求吧。

class Solution {
    public String reverseLeftWords(String s, int n) {
        String res = "";
        for(int i = n; i < s.length(); i++)
            res += s.charAt(i);
        for(int i = 0; i < n; i++)
            res += s.charAt(i);
        return res;
    }
}

459. 重复的子字符串

精简代码版本

思路和代码实现

如果您的字符串 S 包含一个重复的子字符串，那么这意味着您可以多次 “移位和换行”`您的字符串，并使其与原始字符串匹配。

例如：abcabc

移位一次：cabcab
移位两次：bcabca
移位三次：abcabc

现在字符串和原字符串匹配了，所以可以得出结论存在重复的子串。

基于这个思想，可以每次移动k个字符，直到匹配移动 length - 1 次。但是这样对于重复字符串很长的字符串，效率会非常低。在 LeetCode 中执行时间超时了。

为了避免这种无用的环绕，可以创建一个新的字符串 str，它等于原来的字符串 S 再加上 S 自身，这样其实就包含了所有移动的字符串。

比如字符串：S = acd，那么 str = S + S = acdacd

acd 移动的可能：dac、cda。其实都包含在了 str 中了。就像一个滑动窗口

一开始 acd (acd) ，移动一次 ac(dac)d，移动两次 a(cda)cd。循环结束

所以可以直接判断 str 中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。

——转自leetcode题解

class Solution {
   public boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
	}
}

不过这种方法需要证明其两个s字符串叠加的充分必要性，细节挺多的。不赘述，官网题解很清晰，不记得再看看。

优化的KMP算法

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return kmp(s);
    }

    public boolean kmp(String pattern) {
        int n = pattern.length();
        int[] fail = new int[n];
        Arrays.fill(fail, -1);
        for (int i = 1; i < n; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                fail[i] = j + 1;
            }
        }
        return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
    }
}

KMP算法想要彻底理解掌握必须阅读较为晦涩的书籍和原理，推荐读者看一下王道考研的KMP算法，方便快速掌握上手。这里就不赘述了，也说不清楚。代码仅供自己复习使用。