Leetcode question brushing 04 string

character string

Basic knowledge of

brief introduction

1. Introduce

character string ： It is called string for short , Is a finite sequence of zero or more characters . It is generally recorded as s = “a1a2…an”

• String name ： In the string definition s Is the name of the string
• The value of the string ："a1a2…an" The character sequence is the value of the string , Usually enclosed in double quotation marks
• Character variables ： The element at each position of the string is a character variable . character ai It could be letters 、 Numbers or other characters .i Is the position of the character in the string .
• Length of string ： The number of characters in the string n It is called the length of the string
• Empty string ： A zero character string is also called an empty string , Its length is 0, It can be expressed as ""
• Substring ： The subsequence of any consecutive characters in a string is called the substring of the string . And there are two special substrings , Prefix and suffix
• Main string ： A string containing a substring is correspondingly called a main string

According to the characteristics of the string , String problems can be divided into the following ：

• String matching problem
• Substring related problems
• Prefix / Suffix related issues
• Palindrome string related problems
• Subsequence related problems

2. String comparison

The comparison between strings is through the comparison between the characters that make up the string Character encoding To decide , Character coding refers to the sequence number of characters in the corresponding character set .

def strcmp(str1, str2):
    index1, index2 = 0, 0
    while index1 < len(str1) and index2 < len(str2):
        if ord(str1[index1]) == ord(str2[index2]):
            index1 += 1
            index2 += 2
        elif ord(str1[index1]) < ord(str2[index2]):
            return -1
        else:
            return 1
    
    if len(str1) < len(str2):
        return -1
    elif len(str1) > len(str2):
        return 1
    else:
        return 0

Character encoding ： The common characters used in computers are ASCII code , But it can only solve the problem of English language . In order to solve the problem of Chinese coding , Our country has formulated GB2312、GBK、GB18030 And other Chinese coding standards , To solve the world's language problems , There is Unicode code , common Unicode Encoding is UTF-8, Put one Unicode Characters are encoded into... According to different number sizes 1-6 Bytes , Common English letters are encoded as 1 Bytes , Chinese characters are usually 3 Bytes .

3. Storage structure of string

The storage structure of string is the same as that of linear table , It is divided into sequential storage structure and chain storage structure

String matching problem

string matching ： Also known as pattern matching . It can be simply understood as , Given string T and p, In the main string T Find substrings in p. Main string T Is called a text string , Substring p It's called a pattern string .

According to the number of pattern strings , String matching problem is divided into single pattern string matching problem and multi pattern string matching problem .

1. Single pattern string matching problem

Definition ： Given a string of text T=t1t2…tn, Given a particular pattern string p=p1p2…pn. Request from text string T Find a specific pattern string p All occurrences of .

• Prefix based search method ： Read text characters from front to back in the search window , The longest common prefix for text and pattern strings in the search window .

  • The famous KMP Algorithms and faster Shift-Or The algorithm uses this method .

• Suffix based search method ： In the search window, from back to front （ Follow the reverse of the text ） Read in text characters one by one , The longest common suffix for text and pattern strings in the search window . Using this search algorithm, you can skip some text characters , Thus, it has a sub linear average time complexity .

  • The famous BM Algorithm 、Horspool Algorithm 、Sunday The algorithm uses this method

• Search method based on substring ： Read in text characters one by one from back to front in the search window , The search satisfies the suffix of the text in the window , It is also the longest string of the substring of the pattern string . The method also has a sub linear average time complexity . The main drawback is the need to identify all substrings of the pattern string , It's a very complicated problem .

  • Rabin-Karp Algorithm 、BDM Algorithm 、BNDM Algorithm and BOM The algorithm uses this idea , among Rabin-Karp The algorithm uses a hash based substring search algorithm .

2. Multi pattern string matching problem

Most of the multi pattern matching algorithms use a basic data structure ： Dictionary tree （Trie）. The famous AC Automata is just KMP Based on the algorithm , Combined with dictionary tree structure . and AC Automata algorithm is also one of the most effective algorithms in multi pattern string matching algorithm .

So learn the multi pattern matching algorithm , The key point is to master the dictionary tree and AC Automata algorithm .

3. Single mode string naive matching algorithm

Brute Force Algorithm ： Violent matching algorithm , It can also be called naive matching algorithm .

BF Algorithmic thought ：

def bruteForce(T: str, p: str) -> int:
    n, m = len(T), len(p)
    
    i, j = 0, 0
    while i < n and j < m:
        if T[i] == p[j]:
            i += 1
            j += 1
        else:
            i = i - (j - 1)
            j = 0
    if j == m:
        return i - j
    return -1

The worst time complexity is O(m * n), The optimal time complexity is O(m), Average time complexity O(n + m)

4. Single mode string KMP matching algorithm

KMP Algorithmic thought ： For a given text string T And mode string p, When a text string is found T A character and pattern string p When it doesn't match , You can use the information after matching failure , Minimize the number of matches between pattern string and text string , Avoid fallback of text string position , In order to achieve the purpose of rapid matching .

Defects of naive matching algorithm ： When the text string does not match a character of the pattern string , Pointer to text string i You need to go back to the next position where you matched the start position .

KMP Algorithm improvement ： The information of each matching failure is used , A substring of the main string is equal to a prefix of the pattern string . That is to say T[i: i + j] == p[0: j]

KMP The algorithm utilizes the information of matching failure , For pattern strings p Pretreated , Calculate a partial match table , Use an array next Record . Every time a match fails , Do not return the pointer of the text string i, But according to next Matching failed in array j The value of the previous position of , namely next[j - 1] To determine the number of bits that the pattern string can move to the right .

For example, the pattern string in the above example p stay j=5 Matching failure , Then the text substring T[i: i + 5] And mode string p[0: 5] The characters are consistent , According to the partial matching table next[4] = 2, So don't go back i, It's going to be j Move to subscript 2 The location of , Give Way T[i + 5] aim p[2] Continue comparison .

def generateNext(p: str):
    m = len(p)
    next = [0 for _ in range(m)]
    
    left = 0
    for right in range(1, m):
        while left > 0 and p[left] != p[right]:
            left = next[left - 1]
        if p[left] == p[right]:
            left += 1
        next[right] = left
    return next

def kmp(T: str, p: str) -> int:
    n, m = len(T), len(p)
    next = generateNext(p)
    
    j = 0
    for i in range(n):
        while j > 0 and T[i] != p[j]:
            j = next[j - 1]
        if T[i] == p[j]:
            j += 1
        if j == m:
            return i - j + 1
    return -1

The time complexity is O(n + m)

title

Verify the palindrome string

1. Title Description

Topic link

2. Analysis idea and code

Ideas ： There are two ways ：

• Preprocessing strings , Remove space , Make all the letters lowercase , Then flip the string to determine whether it is equal to the original string .
• Use double pointers to directly determine ,i Point to the first position of the string ,j Point to the last position of the string , Skip if it's not a letter or a number , And then determine i and j Whether lowercase characters are equal , Unequal return false, Otherwise, continue to judge , until i == j return true.

	public boolean isPalindrome(String s) {
    
        StringBuffer sgood = new StringBuffer();
        for (int i = 0; i < s.length(); i ++ ) {
    
            if (Character.isLetterOrDigit(s.charAt(i))) {
    
                sgood.append(Character.toLowerCase(s.charAt(i)));
            }
        }
        
        int l = 0, r = sgood.length() - 1;
        while (l < r) {
    
            if (sgood.charAt(l) != sgood.charAt(r)) return false;
            l ++;
            r --;
        }
        return true;
    }

class Solution:
    def isPalindrome(self, s: str) -> bool:
        n = len(s)
        l, r = 0, n - 1
        
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if l < r:
                if s[l].lower() != s[r].lower():
                    return False
                else:
                    l += 1
                    r -= 1
        
        return True

Flip the words in the string

1. Title Description

Topic link

2. Solution ideas and code

Ideas ：

• Use language specific ： Split string 、 Flip strings 、join etc.
• Write your own function implementation

	public String reverseWords(String s) {
    
        List<String> words = Arrays.asList(s.split("\\s+"));
        Collections.reverse(words);
        return String.join(" ", words);
    }


	public String reverseWords(String s) {
    
        int l = 0, r = s.length() - 1;
        while (l <= r && s.charAt(l) == ' ')    l ++ ;
        while (l <= r && s.charAt(r) == ' ')    r -- ;

        List<String> words = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        while (l <= r) {
    
            if (s.charAt(l) != ' ') {
    
                sb.append(s.charAt(l));
            } else {
    
                if (sb.length() > 0) {
    
                    words.add(sb.toString());
                }
                sb = new StringBuilder();
            }
            l ++ ;
        }

        if (sb.length() > 0)    words.add(sb.toString());

        // reverse
        l = 0;
        r = words.size() - 1;
        while (l < r) {
    
            String tmp = words.get(l);
            words.set(l, words.get(r));
            words.set(r, tmp);
            l ++ ;
            r -- ;
        }

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

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.split()))

Verify palindrome string Ⅱ

1. Title Description

Topic link

2. Solution ideas and code

Greedy double pointer ： The double pointer points to the first position and the last position of the string respectively , Then determine whether the corresponding characters are equal , If it's not equal , There are two cases , One is to delete the left pointer character , One is to delete the right pointer character , Then judge whether it is a palindrome string .

	public boolean validPalindrome(String s) {
    
        int l = 0, r = s.length() - 1;
        while (l < r) {
    
            char c1 = s.charAt(l), c2 = s.charAt(r);
            
            if (c1 == c2) {
    
                l ++ ;
                r -- ;
            } else {
    
                return validPalindrome(s, l, r - 1) || validPalindrome(s, l + 1, r);
            }
        }
        return true;
    }
    
    public boolean validPalindrome(String s, int low, int high) {
    
        for (int i = low, j = high; i < j; i ++ , j -- ) {
    
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def check(low, high):
            i, j = low, high
            while i < j:
                if s[i] != s[j]:
                    return False
                
                i += 1
                j -= 1
            return True
    
        l, r = 0, len(s) - 1
        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                return check(l + 1, r) or check(l, r - 1)
        
        return True

Excel Table column name

1. Title Description

Topic link

2. Solution ideas and code

thought ： It's essentially 26 The question of system . It should be noted that you need to subtract... Before taking the mold 1 Guarantee columnNumber by 26 When to return to 26, instead of 0

	public String convertToTitle(int columnNumber) {
    
        StringBuilder sb = new StringBuilder();
        
        while (columnNumber > 0) {
    
            int c = (columnNumber - 1) % 26 + 1;
            sb.insert(0, (char)(c - 1 + 'A'));
            columnNumber = (columnNumber - c) / 26;
        }
        return sb.toString();
    }

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        ans = list()
        while columnNumber > 0:
            a0 = (columnNumber - 1) % 26 + 1
            ans.append(chr(a0 - 1 + ord('A')))
            columnNumber = (columnNumber - a0) // 26
        return "".join(ans[::-1])

String decoding

1. Title Description

Topic link

2. Solution ideas and code

Ideas ： The processing order is to process the letter in the innermost bracket first , Then deal with the letters on the outside , So use recursive processing . If a digit is encountered , There must be parentheses next , Then recursively parse the following .

You can also use the stack to implement .

class Solution {
    
    String src;
    int ptr;
    
    public String decodeString(String s) {
    
        src = s;
        ptr = 0;
        return getString();
    }
    
    public String getString() {
    
        if (ptr == src.length() || src.charAt(ptr) == ']') {
    
            return "";
        }
        
        char cur = src.charAt(ptr);
        int repTime = 1;
        String res = "";
        
        if (Character.isDigit(cur)) {
    
            repTime = getDigits();
            ptr ++ ;
            String str = getString();
            ptr ++ ;
            while (repTime-- > 0) {
    
                res += str;
            }
        } else if (Character.isLetter(cur)) {
    
            res = String.valueOf(src.charAt(ptr ++ ));
        }
        
        return res + getString();
    }
    
    public int getDigits() {
    
        int res = 0;
        while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
    
            res = res * 10 + src.charAt(ptr ++ ) - '0';
        }
        return res;
    }
}

class Solution:
    def decodeString(self, s: str) -> str:
        NUM = "0123456789"
        stack, num, str_ = [], '', ''
        for i in range(len(s)):
            if s[i] in NUM:
                num += s[i]
                if s[i + 1] not in NUM:
                    stack.append(int(num))
                    num = ''
            elif s[i] == ']':
                str_ = ''
                while stack[-1] != '[':
                    str_ = stack.pop() + str_
                stack.pop()
                stack.append(str_ * stack.pop())
            else:
                stack.append(s[i])
        return "".join(stack)