May brush question 02 - string

Today's brush topic content ： character string

Preface

• An algorithm opens the way to brush the questions of waste materials , Update the problem solution content of the problem brush every day
• Focus on personal understanding , Look at the difficulty and update the number of questions
• The title comes from Li Kou
• New column , Try to work out at least one question every day =v=
• Language java、python、c\c++

---

One 、 Today's topic

1. 500. Keyboard line *****
2. 1160. spell the words *****
3. 1047. Delete all adjacent duplicates in the string *****
4. 1935. The maximum number of words that can be entered *****

Two 、 Their thinking

1. 500. Keyboard line *****

1. Use three strings to record the characters of each keyboard line
2. Confirm the character line by the first character of each word
3. Verify whether the subsequent characters are on the same character line
4. If in the same character line , Add the result to the result list

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        str1 = "qwertyuiopQWERTYUIOP"
        str2 = "asdfghjklASDFGHJKLK"
        str3 = "zxcvbnmZXCVBNM"
        ret = []
        #  Confirm which keyboard line comes from by the beginning of each word 
        for word in words:
            flag = True  #  Identify whether the current word comes from the same keyboard line 
            if word[0] in str1:
                for i in range(1, len(word)):
                    if word[i] not in str1:
                        flag = False
                        break
            elif word[0] in str2:
                for i in range(1, len(word)):
                    if word[i] not in str2:
                        flag = False
                        break
            elif word[0] in str3:
                for i in range(1, len(word)):
                    if word[i] not in str3:
                        flag = False
                        break
            if flag:
                ret.append(word)  #  If it comes from the same keyboard line 
        
        return ret

---

2. 1160. spell the words *****

1. Use one hash Table to record the mastered characters
2. Traverse each letter of each word , use flag To identify the current word
3. Traverse all characters of the current word , Once a character is not in the mastered character ,flag by false, Exit the current loop
4. The next word needs to be restored hash surface , Use deep copy

class Solution {
    
    public int countCharacters(String[] words, String chars) {
    
        int[] hash = new int[256];
        //  Use one hash Table to store learned vocabulary 
        for(char c: chars.toCharArray()){
    
            hash[c]++;
        }
        int ret = 0;  //  Count the number of letters 
        int[] temp = new int[256];
        for (String word: words){
    
            boolean flag = true;
            //  Restore the original hash surface 
            System.arraycopy(hash, 0, temp, 0, hash.length);
            for (char w: word.toCharArray()){
    
                if (temp[w] <= 0){
    
                    flag = false;
                    break;
                } else{
    
                    temp[w]--;
                }
            }
            //  If every character in the word is in the mastered string 
            if (flag){
    
                ret += word.length();
            }
        }
        
        return ret;
    }
}

---

3. 1047. Delete all adjacent duplicates in the string *****

1. Define two adjacent pointers l, r, Move two pointers by sliding the window
2. It should be noted that , When the left pointer l Greater than 0 when , At this time, the characters of the left and right pointers are the same , After deleting the same character, the left and right pointers should be returned
3. Otherwise, move the left and right pointers to the right

class Solution {
    
    public String removeDuplicates(String s) {
    
        int l = 0;
        int r = 1;
        int n = s.length();
        StringBuffer sb = new StringBuffer(s);  //  Initialization result 
        while(r < sb.length() && l < sb.length()){
    
            if (sb.charAt(l) == sb.charAt(r)){
    
                sb.deleteCharAt(l);
                sb.deleteCharAt(l);
                //  If the left pointer is greater than 0, The left and right pointers should be returned by one digit at the same time 
                if (l > 0){
    
                    l--;
                    r--;
                }
            }else{
    
                l++;
                r++;
            }
        }
        return sb.toString();
    }
}

---

4. 1935. The maximum number of words that can be entered *****

1. Divide the string into word arrays through spaces
2. Traverse the characters of each word in the word array
3. Once a character is found to belong to a broken keyboard key , Skip the character , Otherwise, the result will be count+1

class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        words = text.split(" ")
        count = 0
        for word in words:
            flag = True
            for char in word:
                if char in brokenLetters:
                    flag = False
                    break
            if flag:
                count += 1
                
        return count