leetcode--字符串专栏

题目速览

附有leetcode的链接

344. 反转字符串

541. 反转字符串II

剑指 Offer 05.替换空格

151. 翻转字符串里的单词

剑指Offer58-II.左旋转字符串

28.实现 strStr()

459. 重复的子字符串

859. 亲密字符串

748. 最短补全词

分题讲解

344反转字符串

如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数

如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

java复制代码    public void reverseString(char[] s) {
        int head = 0;
        int end = s.length - 1;
        char tmp;
        while (head < end){
            tmp = s[end];
            s[end] = s[head];
            s[head] = tmp;
            head++;
            end--;
        }
    }

541反转字符串ii

java复制代码class Solution {
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        int len = s.length();
        int head = 0;
        int last = 2 * k - 1;
        while (last <= len - 1){
            reverse(head, head + k - 1, arr);
            last += 2 * k;
            head += 2 * k;
        }
        int end = (len - 1 - head < k) ? len - 1 : head + k - 1;
        reverse(head, end, arr);
        return String.valueOf(arr);
    }

    public void reverse(int first, int end, char[] arr){
        while (first < end){
            char tmp = arr[first];
            arr[first] = arr[end];
            arr[end] = tmp;
            first++;
            end--;
        }
    }
}

谋而后定
先分块

• 够2k
  交换函数
• 不够2k
  小于k—交换函数
  大于k,小于2k—交换函数

剑指Offer5替换空格

java复制代码class Solution {
    public String replaceSpace(String s) {
    	//用StringBuffer单线程更快
        StringBuffer stb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char point = s.charAt(i); 
            if (point == ' '){
                stb.append("%20");
            }else {
                stb.append(point);
            }
        }
        return stb.toString();
    }
}

这里提供另一种思路：
1.可以扩充原始字符串空间变成可以装下新变化的字符。
2.定位原始字符串的最后一个字符
3.定位新字符串最后一个字符
4.对比复制

java复制代码public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

151. 翻转字符串里的单词

法一：比较水，利用字符串中split函数，额外O(N)空间，最后串起来，要注意，去掉最后的空格，以及存在连续的分割符的时候例如两个空格，分割之后就是“”，用.equals()判断
法二：反转全部的字符，最后在反转其中的单词，这个最后的时间复杂度是O(1)。分步骤执行，最开始要除去多余的空格。反转全部字符串。反转其中的单词。

java复制代码	//法一
    public static String reverseWords(String s) {
        String[] s1 = s.split(" ");
        StringBuffer stb = new StringBuffer();
        for (int i = s1.length - 1; i >= 0; i--){
            if (!s1[i].equals("")) {
                stb.append(s1[i] + " ");
            }
        }
        //移除最后一个空格
        return stb.toString().substring(0,stb.length() - 1);
    }

    public static void main(String[] args) {
        System.out.println(reverseWords("We      are happy"));//happy are We
    }

java复制代码//法二
class Solution {
   /**
     * 不使用Java内置方法实现
     * <p>
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
        // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

剑指Offer58-II.左旋转字符串

法一：比较水，就是利用substring
其实使用substr 和 反转 时间复杂度是一样的 ，都是O(n)，但是使用substr申请了额外空间，所以空间复杂度是O(n)，而反转方法的空间复杂度是O(1)。
法二：不使用substring可以直接利用反转来，一个比较有意思的思路就是:

java复制代码//法一：
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder();
        sb.append(s.substring(n)+s.substring(0,n));
        return sb.toString();
    }
//法二：
class Solution {
    public String reverseLeftWords(String s, int n) {
        int len=s.length();
        StringBuilder sb=new StringBuilder(s);
        reverseString(sb,0,n-1);
        reverseString(sb,n,len-1);
        return sb.reverse().toString();
    }
     public void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
            }
        }
}

28. 实现 strStr()

暴力解法必定是不行的，这里有一个好的api，就是KMP算法，很重要，建议背住
KMP算法

java复制代码    public static int strStr(String haystack, String needle) {
        if (needle.equals("")) return 0;//每个题目要求不一样，伺机而动
        if (haystack.length() == 0 || needle.length() == 0 || haystack.length() < needle.length()) return -1;
        char[] str1 = haystack.toCharArray();
        char[] str2 = needle.toCharArray();
        //建立next[i]数组，存储在str2第i个字符前,最长的（前缀和后缀相等）的长度。注意字符串本身不会包括在里面
        int[] next = new int[str2.length];
        next[0] = -1;
        if (str2.length > 1){//防止str2只有一个字符
            next[1] = 0;
        }
        int i = 2;
        //初始cn记录的是next[i- 1]的值，因为这里i的初始是2，所以next[i-1] = 0,所以cn = 0;
        int cn = 0;
        while (i < str2.length){
            if (str2[i - 1] == str2[cn]){
                next[i++] = ++cn;
            }else if (cn == 0){
                next[i++] = 0;
            }else {
                cn = next[cn];
            }
        }
        //利用next[] 数组求解字符串匹配问题
        int t1 = 0; int t2 = 0;
        while (t1 < str1.length && t2 < str2.length){
            if (str1[t1] == str2[t2]){
                t1++;
                t2++;
            }else if (t2 == 0){
                t1++;
            }else {
                t2 = next[t2];
            }
        }
        return t2 == str2.length ? t1 - t2 : -1;
    }

    public static void main(String[] args) {
        String haystack = "abcdeabcfee";
        String needle = "d";
        System.out.println(strStr(haystack,needle));
    }

29. 重复的子字符串

自己一上来还真的是不知道要用KMP算法，但是因为是要看是不是重复的组成字符串，那么next[]的数组绝对是有规律的。可以运行几个next[]数组看看可以得到如下的规律:

java复制代码public static boolean repeatedSubstringPattern(String s) {
        if (s.length() < 2) return false;
        //可以利用KMP算法，以为next[]数组中一定会有相应的规律
        char[] arr = s.toCharArray();
        int n = s.length();
        int[] next = new int[n + 1];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i <= n){
            if (arr[i - 1] == arr[cn]){
                next[i++] = ++cn;
            }else if (cn == 0){
                next[i++] = 0;
            }else {
                cn = next[cn];
            }
        }
        for (int h : next){
            System.out.println(h);
        }
        if (next[n] != 0 && n % (n - (next[n])) == 0){
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String haystack = "abcabcabc";
        System.out.println(repeatedSubstringPattern(haystack));
    }

859. 亲密字符串

思路：
自己第一次只想到了遍历，知道这是必定错误的做法。
现在看来，可以想想，满足什么条件，就可以充分的得出结果，不需要模拟遍历
满足亲密字符串的条件：

1. str1 和 str2的长度、词频必然相同
2. 对于每一个i位置，只能有两个词不同 || 当没有不同词的时候，重复的词大于1

代码：

java复制代码    public static boolean buddyStrings(String s, String goal) {
        int len1 = s.length();
        int len2 = goal.length();
        if (len1 != len2) return false;
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        int dif = 0;
        for(int i = 0; i < len1; i++){
            count1[s.charAt(i) - 'a']++;
            count2[goal.charAt(i) - 'a']++;
            //记录不同的次数
            if (s.charAt(i) != goal.charAt(i)){
                dif++;
                //这里会有一个很大的漏洞，就是如果是aaabb,aaacc就会返回正确，
                //判断的太早了，还需要判断词频是不是一样，就可以杜绝这个现象
//                if (dif > 2) return false;
            }
        }
        //判断词频
        boolean ok = false;
        for (int i = 0; i < 26; i++){
            if (count1[i] != count2[i]) return false;
            //判断谁都一样，保证词频相同的话
            if (count1[i] > 1) ok = true;
        }
        return dif == 2 || (dif == 0 && ok == true);
    }

748. 最短补全词

思路：
自己第一次想到了如下的步骤：

1. lisense字频统计
2. 遍历words中的每一个word,然后字符统计
3. 比较（并记录最小符合条件的word长度）

但是在3中，自己为了追求空间复杂度，想着复用一个int[26],在这个基础上加加减减，但是显得代码很乱。还不如每次新建一个每次刷新，也是用的一个int[26]，所以代码看的清楚也很重要

代码：
注意：
Character.isLetter(licensePlate.charAt(i)) 判断字符是不是字母
Character.toLowerCase(licensePlate.charAt(i)) 将可能的大写字母转为小写字母

java复制代码class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] charNum = new int[26];
        for (int i = 0; i < licensePlate.length(); i++) {
            if (Character.isLetter(licensePlate.charAt(i))) {
                ++charNum[Character.toLowerCase(licensePlate.charAt(i)) - 'a'];
            }
        }
        int len = Integer.MAX_VALUE;
        int idx = -1;
        for (int i = 0; i < words.length; i++){
            int[] charNum2 = new int[26];
            for (int j = 0; j < words[i].length(); j++){
                ++charNum2[words[i].charAt(j) - 'a'];
            }

            boolean ok = true;
            for (int k = 0; k < 26; k++){
                if (charNum[k] > charNum2[k]){
                    ok = false;
                    break;
                }
            }
            if (ok && (idx < 0 || words[i].length() < words[idx].length())){
                idx = i;
            }
        }
        return words[idx];
    }
}

总结

1. 建议如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。
2. 双指针法在数组，链表和字符串中很常用。很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作
3. 当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章，有一个思路：先整体反转再局部反转、先局部反转再整体反转
4. KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。—-字符串中最重要的算法

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有