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…