[toc]

String

344. Reverse String

Easy

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

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

541. Reverse String II

Easy

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

class Solution {
    public String reverseStr(String s, int k) {
        char[] ss = s.toCharArray();
        for(int i = 0 ; i < ss.length; i = i + 2*k){
            if(i+k-1 < ss.length){  //!!!!!
                reverse(ss, i, i+k-1);
            }else{
                reverse(ss, i, ss.length-1);
            }
            
        }
        return new String(ss);
    }
    public void reverse(char[] s, int start, int end){
        while(start < end){
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
    }
}

replace number

https://programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

151. Reverse Words in a String

Medium

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

class Solution {
    public String reverseWords(String s) {
        s = removeSpace(s);
        char[] ss = s.toCharArray();
        reverse(ss, 0, s.length()-1);
        int left = 0;
        int right = 0;
        for(int i = 0 ; i < ss.length; i++){
            if(i == ss.length - 1 || ss[i] == ' '){
                if(i == ss.length - 1){
                    right = i;
                }else{
                    right = i - 1;
                }
                reverse(ss, left, right);
                left = i + 1;
            }
        }
        return new String(ss);
    }
    public void reverse(char[] s, int start, int end){
        while(start < end){
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
    }
    public static String removeSpace(String s){
        StringBuilder sb = new StringBuilder();
        int start = 0 ;
        int end = s.length() - 1;
        while(s.charAt(start) ==(' ')) start++;   //!!!!!!!!!!!
        while(s.charAt(end) ==(' ')) end--;   //!!!!!!!!!!!
        for(int i = start; i <= end; i++){
            if(s.charAt(i) != ' '){
                sb.append(s.charAt(i));
            }
            if(s.charAt(i) == ' ' && s.charAt(i-1) != ' '){ //!!!!!!
                sb.append(" ");

            }
        }
        return sb.toString();
    }
}

right-rotated string

https://programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html#%E6%80%9D%E8%B7%AF

KMP

What is KMP?

The Knuth-Morris-Pratt algorithm is a string searching algorithm. It efficiently finds occurrences of a “pattern” string within a longer “text” string. Unlike some other string search algorithms like the naive or brute-force method, KMP avoids unnecessary comparisons by utilizing information about the pattern itself.

https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E6%80%9D%E8%B7%AF

class Solution {
    //前缀表（不减一）Java实现
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) 
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) 
                j++;
            next[i] = j; 
        }
    }
}