The first question is : 290. Rules of words

LeetCode: 290. Rules of words

describe :
Give a rule pattern And a string s , Judge s Follow the same rule .

there follow Finger perfect match , for example , pattern Each letter and string in s There is a two-way connection between each non empty word in .

Their thinking :

1. Here we use hash table to solve problems .
2. First of all, will s String into string array .
3. If At this time, the length of the string array and pattern The length is different , Go straight back to false
4. If the current hash table does not exist pattern.charAt(i) The elements of , First judge , Corresponding value Whether the value repeats . If it repeats , Just go back to false. There is no repetition Add directly to In the hash table .
5. If... Exists in the current hash table pattern.charAt(i) The elements of , Just check the corresponding value Whether the value is the same as the current str[i] Whether it is equal or not , Equality means that the correspondence is regular . Otherwise return to false

Code implementation :

class Solution {
    
    public boolean wordPattern(String pattern, String s) {
    
        String[] str = s.split(" ");
        if(pattern.length() != str.length) return false;
        Map<Character,String> map = new HashMap<>();
        for(int i = 0;i < str.length ;i++){
    
            if(!map.containsKey(pattern.charAt(i))) {
    
                if(map.containsValue(str[i])){
    
                    return false;
                }else{
    
                    map.put(pattern.charAt(i),str[i]);
                }
            }
        }
        for(int i = 0; i < str.length; i++) {
    
            if(!map.get(pattern.charAt(i)).equals(str[i])){
    
                return false;
            }
        }
        return true;
    }
}

The second question is : 402. move away K Digit number

LeetCode: 402. move away K Digit number

describe :
Give you a nonnegative integer expressed as a string num And an integer k , Remove the k Digit number , Keep the remaining numbers to a minimum . Please return the smallest number as a string .

Their thinking :

1. Here, first of all, the current num String to judge , If k Equal to the length of the string return "0"
2. Use an auxiliary stack to solve problems .
3. If the current corresponding number , It should be larger than the top element , Just go straight out of the stack .
4. otherwise , Check whether the current number is 0, If 0, And If the stack is not empty, enter it ,
5. The current array is not 0 Just go straight to the stack .
6. After traversing once see k Is it empty , That is, whether the number of times out of the stack is k Time .
7. here k Not empty Out of the stack again .
8. If the stack is empty , Just go back to “0”
9. String splicing is performed when the stack is not empty .

Code implementation :

class Solution {
    
    public String removeKdigits(String num, int k) {
    
        if(k == num.length()) return "0";
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < num.length(); i++) {
    
            int tmp = num.charAt(i) -'0';
            while(k != 0 && !stack.isEmpty() && stack.peek() > tmp) {
    
                stack.pop();
                k--;
            }
            if(tmp != 0 || !stack.isEmpty()) {
    
                stack.push(tmp);
            }
        }
        while(k != 0 && !stack.isEmpty()) {
    
            stack.pop();
            k--;
        }
        if(stack.isEmpty()) return "0";
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()) {
    
            res.append(stack.pop());
        } 
        return res.reverse().toString();
    }
}

Third question : 409. Longest palindrome

LeetCode: 409. Longest palindrome

describe :
Given a string of uppercase and lowercase letters s , return Constructed from these letters The longest palindrome string .

In the process of construction , Please note that Case sensitive . such as “Aa” Can't be treated as a palindrome string .

Their thinking :

1. First, use a hash table to record the number of occurrences of each character .
2. If a character appears an even number of times , Directly add the number of occurrences of this character to the result set .
3. If a character appears an odd number of times , To add this number -1 Time . for example aaa, There is 3 Time , But you can use his occasional times , 3-1=2.
4. End of traversal , If there is an odd number , then +1, For example, you recorded aaa, Only occasionally recorded , After that , You can add it again a

Code implementation :

class Solution {
    
    public int longestPalindrome(String s) {
    
        Map<Character,Integer> map = new HashMap<>();
        for(char ch : s.toCharArray()) {
    
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        int count = 0;
        int ret = 0;
        for(Map.Entry<Character,Integer> entry : map.entrySet()) {
    
            if(entry.getValue() % 2 == 0) {
    
                count += entry.getValue();
            }else{
    
                count += entry.getValue()-1;
                ret = 1;
            }
        }
        return count + ret;
    }
}

Fourth question : 459. Repeated substrings

LeetCode: 459. Repeated substrings

describe :
Given a non empty string s , Check whether it can be formed by repeating one of its substrings multiple times .

Their thinking :

1. Whether it can be refactored here can be understood as , Move the left character to the right , Whether it can be changed into the original character .
2. for example abab, The first move is baba, The second move is abab, The third move is baba.
3. Here you can make the string s Splice twice , Then remove the head and tail , And look for Whether there is s

Code implementation :

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

Fifth question : 516. The longest palindrome subsequence

LeetCode: 516. The longest palindrome subsequence

describe :
Give you a string s , Find the longest palindrome subsequence , And return the length of the sequence .

Subsequence is defined as ： Without changing the order of the remaining characters , A sequence formed by deleting some characters or not deleting any characters .

Their thinking :

1. Here we use dynamic programming to solve problems .
2. state F(i,j) : Express i ~ j The length of the longest palindrome subsequence .
3. State transition equation :
   • F(i,j) = F(i+1)(j-1) + 2 (s[i] = s[j])
   • F(i,j) = Math.max(F(i+1)(j),F(i)(j-1)) (s[i] != s[j])
4. The initial state : F(i,i) = 1
5. Return results : F(0,len-1)
    
   Because some characters can be deleted , All if s[i] != s[j] When , You can count one more character .

Code implementation :

class Solution {
    
    public int longestPalindromeSubseq(String s) {
    
        int[][] dp = new int[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++){
    
            dp[i][i] = 1;
        }
        for(int i = s.length()-2; i >= 0; i--) {
    
            for(int j = i+1; j < s.length(); j++){
    
                if(s.charAt(i) == s.charAt(j)) {
    
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
    
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
}

Sixth question : 520. Detect capital letters

LeetCode: 520. Detect capital letters

describe :
We define , When , The capitalization of words is correct ：

• All the letters are uppercase , such as “USA” .
• All the letters in a word are not capitalized , such as “leetcode” .
• If a word contains more than one letter , Only the first letter is capitalized , such as “Google” .

Give you a string word . If capitalized correctly , return true ; otherwise , return false .

Their thinking :

1. Use upCount Record the number of times capital letters appear .
2. Use lowCount Record the number of lowercase letters .
3. Traversal string ,
4. If upCount == word,length() , Then the conditions are met 1.
5. If lowCount == word.length(), Then the conditions are met 2.
6. If upCount == 1 && word.charAt(0) As the capital , Then the conditions are met 3.
7. Not satisfied with this 3 individual Just go back to false

Code implementation :

class Solution {
    
    public boolean detectCapitalUse(String word) {
    
        int upCount = 0;
        int lowCount = 0;
        for(char ch : word.toCharArray()){
    
            if(ch>='a' && ch<='z') {
    
                lowCount++;
            }else{
    
                upCount++;
            }
        }
        if(lowCount == word.length()) {
    
            return true;
        }
        if(upCount == word.length()) {
    
            return true;
        }
        if(upCount == 1 && word.charAt(0) >= 'A' && word.charAt(0) <= 'Z'){
    
            return true;
        }
        return false;
    }
}