Leetcode question brushing: hash table 01 (valid Letter ectopic words)

242. Effective alphabetic words

Force button topic link

Given two strings s and t , Write a function to determine t Whether it is s Letter heteronym of .

Example 1:
Input : s = “anagram”, t = “nagaram”
Output : true

Example 2:
Input : s = “rat”, t = “car”
Output : false

explain :
You can assume that the string contains only lowercase letters .

The first idea to get this question is to divide each string into character arrays , two for Circular bubble sort , Last bit by bit comparison

 /** *  Given two strings  s  and  t , Write a function to determine  t  Whether it is  s  Letter heteronym of . *  Be careful ： if s  and  t Each character in the has the same number of occurrences , said s  and  t They are mutually alphabetic words . *  source ： Power button （LeetCode） *  link ：https://leetcode.cn/problems/valid-anagram * 1 <= s.length, t.length <= 5 * 10^4 * s  and  t  Only lowercase letters  * * @param s * @param t * @return */
    public static boolean isAnagram(String s, String t) {
    
        // If the length is different , Then it must not be equal 
        if (s.length() != t.length()) {
    
            return false;
        }
        // Both strings are split into character arrays , Then sort , Compare them bit by bit 
        char[] arrS = s.toCharArray();
        char[] arrT = t.toCharArray();
        for (int i = 0; i < arrS.length - 1; i++) {
    
            for (int j = i + 1; j < arrS.length; j++) {
    
                if (arrS[i] > arrS[j]) {
    
                    char temp = arrS[i];
                    arrS[i] = arrS[j];
                    arrS[j] = temp;
                }
                if (arrT[i] > arrT[j]) {
    
                    char temp = arrT[i];
                    arrT[i] = arrT[j];
                    arrT[j] = temp;
                }
            }
        }
        for (int i = 0; i <arrS.length ; i++) {
    
            if(arrS[i]!=arrT[i]) {
    
                return false;
            }
        }
        return true;
    }

The result is obviously undesirable , Although the idea is right , But overtime

Change the way of thinking , Altogether 26 Lowercase letters , It is better to use an array to record every occurrence at this time

    /** *  Given two strings  s  and  t , Write a function to determine  t  Whether it is  s  Letter heteronym of . *  Be careful ： if s  and  t Each character in the has the same number of occurrences , said s  and  t They are mutually alphabetic words . *  source ： Power button （LeetCode） *  link ：https://leetcode.cn/problems/valid-anagram * 1 <= s.length, t.length <= 5 * 10^4 * s  and  t  Only lowercase letters  * * @param s * @param t * @return */
    public static boolean isAnagram(String s, String t) {
    
        // If the length is different , Then it must not be equal 
        if (s.length() != t.length()) {
    
            return false;
        }
        // Create an alphabet with matching digits 
        char[] arrS = s.toCharArray();
        char[] arrT = t.toCharArray();
        int[] numS = new int[26];
        int[] numT = new int[26];
        for (int i = 0; i < arrS.length; i++) {
    
            numS[arrS[i] % 26] += 1;
            numT[arrT[i] % 26] += 1;
        }
        for (int i = 0; i < 26; i++) {
    
            if(numS[i]!=numT[i]) {
    
                return false;
            }
        }
        return true;
    }

The effect is much better . Look at the solution , It is similar to me .

class Solution {
    
    public boolean isAnagram(String s, String t) {
    

        int[] record = new int[26];
        for (char c : s.toCharArray()) {
    
            record[c - 'a'] += 1;
        }
        for (char c : t.toCharArray()) {
    
            record[c - 'a'] -= 1;
        }
        for (int i : record) {
    
            if (i != 0) {
    
                return false;
            }
        }
        return true;
    }
}

It's just that the solution uses a counting array , Add... For the first time 1, Second time subtraction 1. About the same .