Valid letter heterotopic word

Subject address: leetcode-cn.com/problems/va…

Given two strings s and t, write a function to determine whether t is an alphabetic allotopic of S. (26 lowercase letters)

Example 1:

Enter: s ="anagram", t = "nagaram"Output:true
Copy the code

Example 2:

Enter: s ="rat", t = "car"Output:false
Copy the code

Note: You can assume that strings contain only lowercase letters.

Advanced: What if the input string contains Unicode characters? Can you adjust your solution to this situation?

Solution 1: Hash table

This is also a lookup operation, so it’s a hash table. If two strings have the same letters and are in different positions, use a Hash. And finally the key is the same and the value is the same, so the two values are the same and the value is equal to 0. Do it with a map

public boolean isAnagram(String s, String t) {
    char[] ss = s.toCharArray();
    char[] tt = t.toCharArray();
    // Just walk away
    if(ss.length ! = tt.length) {return false;
    }
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    for (int i = 0; i < ss.length; i++) {
        char c1 = ss[i];
        char c2 = tt[i];
        // If it is true, the last key value is 0
        map.put(c1, map.getOrDefault(c1, 0) + 1);
        map.put(c2, map.getOrDefault(c2, 0) - 1);
    }
    // Walk through the table, there are either more or less heterotopic words
    for (int i = 0; i < map.size(); i++) {
        if(map.get(tt[i]) ! =0) {
            return false; }}return true;
}
Copy the code

Solution 2: Arrays

So if you can do it with a HashMap like we did before you have to think about whether you can do it with an array, but the limitation of using an array is that it’s fixed. So if the record key is fixed not much can be used. So this is 26 letters

public boolean isAnagram(String s, String t) {
    char[] ss = s.toCharArray();
    char[] tt = t.toCharArray();
	// Just walk away
    if(ss.length ! = tt.length) {return false;
    }
    int[] table = new int[26];
    for (int i = 0; i < ss.length; i++) {
        int c1 = ss[i] - "a";
        int c2 = tt[i] - "a";
        // If it is true, the last key value is 0
        table[c1]++;
        table[c2]--;
    }
    // Walk through the table, there are either more or less heterotopic words
    for (int i = 0; i < 26; i++) {
        if(table[i] ! =0) {
            return false; }}return true;
}
Copy the code

Solution three: sort

If the string is in a different position, it is equal to the number of characters in the string. But sorting is only nlogn, so it’s not optimal but solving this problem with library functions is relatively simple and straightforward, and you can even return one sentence directly

public boolean isAnagram(String s, String t) {
	if(s.length() ! = t.length()) {return false;
    }
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}
Copy the code

conclusion

In general, solution 2 is optimal, but only when the characters are lowercase. The other two solutions are generic unlimited characters.

String of LeetCode daily: 242 effective letters ectopic word | creator training camp The campaign is under way…