代码随想录字符串 Java-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录字符串 Java。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

（简单）344. 反转字符串

代码随想录字符串 Java

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
}

复杂度分析：

时间复杂度：O(N)，其中N为字符数组的长度。一共执行了N/2次的交换
空间复杂度：O(1)，只使用了常数空间来存放若干变量

（简单）541. 反转字符串||

代码随想录字符串 Java
我的思路：2k个字符为一组，先将前k个字符（或者不足k个字符）添加到StringBuilder中，然后调用reverse()方法，然后再将后k个字符（或者不足2k个字符）添加到StringBuilder中，最后在将这一组作为一个整体，添加到答案中

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        int i = 0;
        StringBuilder stringBuilder = new StringBuilder();
        while (i < n) {
            StringBuilder strk = new StringBuilder();
            while (i < n && strk.length() < k) {
                strk.append(s.charAt(i));
                i++;
            }
            strk.reverse();
            while (i < n && strk.length() >= k && strk.length() < 2 * k) {
                strk.append(s.charAt(i));
                i++;
            }
            stringBuilder.append(strk);
        }
        return stringBuilder.toString();
    }
}

代码随想录字符串 Java
我的另一种思路：将字符串s转换成字符数组，然后在字符数组中找到合适的区间进行交换

import java.util.regex.Pattern;

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] charArray = s.toCharArray();
        boolean flag = true;
        int i = 0;
        while (i < n) {
            if (flag) {
                int left = i;
                int right = i + k > n ? n - 1 : i + k - 1;
                while (left < right) {
                    char tmp = charArray[left];
                    charArray[left] = charArray[right];
                    charArray[right] = tmp;
                    left++;
                    right--;
                }
                i = i + k;
                flag = false;
            } else {
                if (i + k >= n) {
                    break;
                } else {
                    i += k;
                    flag = true;
                }
            }
        }
        return new String(charArray);
    }
}

代码随想录字符串 Java
其他写法

也是模拟，反转每个下标从2k的倍数开始的，长度为k的子串。若该子串长度不足k，则反转整个子串。

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] charArray = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(charArray, i, Math.min(i + k, n) - 1);
        }
        return new String(charArray);
    }

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

代码随想录字符串 Java
复杂度分析：

时间复杂度：O(n)，其中n是字符串s的长度
空间复杂度：O(1)和O(n)，取决于使用的语言中字符串类型的性质。如果字符串是可修改的，可以直接在原字符串上进行修改，空间复杂度为O(1)，否则需要使用O(n)的空间将字符串临时转换为可以修改的数据结构（例如数组），空间复杂度为O(n)。

（简单）剑指Offer 05. 替换空格

代码随想录字符串 Java

方法一

class Solution {
    public String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }
}

代码随想录字符串 Java
方法二

class Solution {
    public String replaceSpace(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                stringBuilder.append("%20");
            } else {
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString();
    }
}

代码随想录字符串 Java
其他思路

由于每次替换从1个字符变成3个字符，使用字符数组可方便地进行替换。建立字符数组的长度为s的长度的3倍，这样可保证字符数组可以容纳所有替换后的字符。

class Solution {
    public String replaceSpace(String s) {
        int n = s.length();
        char[] array = new char[n * 3];
        int index = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[index++] = '%';
                array[index++] = '2';
                array[index++] = '0';
            } else {
                array[index++] = c;
            }
        }
        return new String(array, 0, index);
    }
}

代码随想录字符串 Java

（中等）151. 反转字符串中的单词

代码随想录字符串 Java

class Solution {
    public String reverseWords(String s) {
    	//使用trim()去掉首尾的空格，在使用split()按照" "分割
        String[] splits = s.trim().split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = splits.length - 1; i >= 0; i--) {
			//但单词间会有多个空格，遇到splits[i].length==0的直接跳过
            if (splits[i].length() == 0) {
                continue;
            }

            stringBuilder.append(splits[i]);

            if (i != 0) {
                stringBuilder.append(" ");
            }
        }
        return stringBuilder.toString();
    }
}

代码随想录字符串 Java
官方思路，方案一：使用语言特性

很多语言对字符串提供了split拆分、reverse翻转和join连接等方法，因此可以通过调用内置的API完成操作
代码随想录字符串 Java

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

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);
    }
}

复杂度分析：

时间复杂度：O(n)，其中n为输入字符串的长度
空间复杂度：O(n)，用来存储字符串分割之后的结果

官方思路，方法二：自行编写相应的函数

在不同的编程语言中，这些函数是不一样的，主要的差别是有些语言的字符串不可变（如Python、Java），有些语言的字符串可变（如C++）。

对于字符串不可变的语言，首先得把字符串转化成其他可变的数据结构，同时还需要在转化的过程中去除空格。
代码随想录字符串 Java

对于字符串可变的语言，就不需要额外开辟空间了，直接在字符串上原地实现。在这种情况下，反转字符和去除空格可以一起完成。
代码随想录字符串 Java

class Solution {
    public String reverseWords(String s) {
        
        //去除首部、尾部、中间多余字符
        StringBuilder sb = trimSpace(s);
        
        //反转整个字符串
        reverse(sb, 0, sb.length() - 1);
        
        //以空格为分割，反转每一个单词
        reverseEachWord(sb);
        return sb.toString();
    }

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

    private void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, tmp);
            left++;
            right--;
        }
    }

    private StringBuilder trimSpace(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left <= right) {

            //去除字符串开头的空白字符串
            while (left <= right && s.charAt(left) == ' ') {
                left++;
            }

            //去除字符串末尾的空白字符串
            while (left <= right && s.charAt(right) == ' ') {
                right--;
            }

            StringBuilder stringBuilder = new StringBuilder();
            while (left <= right) {
                char c = s.charAt(left);
                if (c != ' ') {
                    stringBuilder.append(c);
                } else if (stringBuilder.charAt(stringBuilder.length() - 1) != ' ') {
                    stringBuilder.append(c);
                }
                left++;
            }
            return stringBuilder;
        }
        return null;
    }
}

代码随想录字符串 Java
复杂度分析：

时间复杂度：O(n)，其中n为输入字符串的长度，因为需要完整遍历字符串
空间复杂度：Java和Python的方法需要O(n)的空间来存储字符出，而C++方法只需要O(1)的额外空间来存放若干变量

官方思路，方法三：双端队列

由于双端队列支持从队列头部插入的方法，因此我们可以沿着字符串一个一个单词处理，然后将单词压入队列头部，再将队列转成字符串即可

代码随想录字符串 Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String reverseWords(String s) {
        int n = s.length();
        int left = 0;
        int right = s.length() - 1;

        //去除字符串开头的空白字符串
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        //去除字符串末尾的空白字符串
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        Deque<String> deque = new ArrayDeque<>();
        StringBuilder word = new StringBuilder();

        while (left <= right) {
            char c = s.charAt(left);
            if (word.length() != 0 && c == ' ') {
                deque.offerFirst(word.toString());
                word.setLength(0);
            } else if (c != ' ') {
                word.append(c);
            }
            ++left;
        }
        deque.offerFirst(word.toString());

        return String.join(" ", deque);
    }
}

代码随想录字符串 Java
复杂度分析：

时间复杂度：O(n)，其中n为输入字符串的长度
空间复杂度：O(n)，双端队列存储单词需要O(n)的空间。

其实这个地方的双端队列和栈是一个意思啊

（简单）剑指 Offer 58 - II. 左旋转字符串

代码随想录字符串 Java
简单来说，就是把字符串截成两段，把这两段交换一下位置，拼接成一个新的字符串返回

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        char[] chars = new char[len];
        int index = 0;
        for (int i = n; i < len; i++) {
            chars[index++] = s.charAt(i);
        }
        for (int i = 0; i < n; i++) {
            chars[index++] = s.charAt(i);
        }
        return new String(chars);

    }
}

代码随想录字符串 Java

class Solution {
    public String reverseLeftWords(String s, int n) {

        int len = s.length();

        StringBuilder stringBuilder = new StringBuilder(len);

        for (int i = n; i < len; i++) {
            stringBuilder.append(s.charAt(i));
        }
        for (int i = 0; i < n; i++) {
            stringBuilder.append(s.charAt(i));
        }

        return stringBuilder.toString();

    }
}

代码随想录字符串 Java

（*中等 - KMP算法）28. 找出字符串中第一个匹配项的下标

代码随想录字符串 Java

最最最传统的字符串匹配问题，脑海中第一反应是KMP算法，但是不记得思路是啥了，所以写了暴力匹配法

class Solution {
    public int strStr(String haystack, String needle) {

        int n = needle.length();
        int h = haystack.length();

        if (n > h) {
            return -1;
        }

        int i = 0;
        int j;
        while (i < h) {
            if (haystack.charAt(i) != needle.charAt(0)) {
                i++;
            } else {
                int k = i + 1;
                j = 1;
                while (k < h && k < i + n && haystack.charAt(k) == needle.charAt(j)) {
                    k++;
                    j++;
                }
                if (k == i + n) {
                    return i;
                } else {
                    i++;
                }
            }
        }
        return -1;
    }
}

代码随想录字符串 Java

暴力法，就是让字符串needle与字符串haystack的所有长度为m的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串进行匹配。如果当前字串匹配成功，就返回当前子串开始的位置即可。如果所有子串都匹配失败，则返回-1

class Solution {
    public int strStr(String haystack, String needle) {

        int m = needle.length();//短的
        int n = haystack.length();//长的

        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}

代码随想录字符串 Java
复杂度分析：

时间复杂度：O(nm)，其中n是字符串haystack的长度，m是字符串needle的长度。最坏情况下需要将字符串needle与字符串haystack的所有长度为m的子串均匹配一次。
空间复杂度：O(1)，只需要常数的空间保存若干变量。

KMP算法

暴力法的时间复杂度是O(mn)，而KMP的时间复杂度是O(m+n)，是因为其能在非完全匹配的过程中提取到有效信息进行复用，以减少重复匹配的消耗

暴力法匹配字符串，当出现不同位置时，将原字符串的指针移动至本次起始点的下一个位置，匹配串的指针移动至起始位置。继续尝试匹配，发现对不上，原串的指针会一直往后移动，知道能够与匹配串对上位置。

import java.util.Arrays;

class Solution {
    public int strStr(String haystack, String needle) {

        int haystackLength = haystack.length();
        int needleLen = needle.length();

        if(needleLen > haystackLength){
            return -1;
        }

        char[] haystackArr = haystack.toCharArray();
        char[] needleArr = needle.toCharArray();
        int[] next = new int[needleLen];
        getNext(next, needle.toCharArray());
        int i = 0;
        int j = 0;
        while (i < haystackLength) {
            if (haystackArr[i] != needleArr[j]) {
                while (j != 0 && haystackArr[i] != needleArr[j]) {
                    j = next[j - 1];
                }
                if (j == 0 && haystackArr[i] != needleArr[j]) {
                    i++;
                }
            } else {
                i++;
                j++;
            }

            if (j == needleLen) {
                return i - j;
            }
        }
        return -1;
    }

    private void getNext(int[] next, char[] arr) {
        int len = arr.length;
        int j = 0;
        int i = 1;
        while (i < len) {
            if (arr[i] == arr[j]) {
                next[i] = j + 1;
                i++;
                j++;
            } else {
                while (j > 0 && arr[i] != arr[j]) {
                    j = next[j - 1];
                }
                if (j == 0 && arr[i] != arr[j]) {
                    next[i] = 0;
                    i++;
                }
            }
        }
    }
}

代码随想录字符串 Java

（*简单 - KMP算法）459. 重复的子字符串

代码随想录字符串 Java

假设原字符串S是由子串s重复N次而成的，则S+S则有子串s重复2N次，那么现在有S=Ns，S+S=2Ns，其中N>=2。如果条件成立，掐头去尾破坏两个s，S+S中至少还有2(N-1)s，又因为N>=2，因此在S+S的索引从[0,length-2]中必出现一次以上

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