LeetCode - 242. Valid Anagram #J

Question

Given two strings s and t, write a function to determine if t is an anagram of s.
For example,s = "anagram", t = "nagaram", return true.s = "rat", t = "car", return false.
Note:You may assume the string contains only lowercase alphabets.

判断字符串t是否为s打乱顺序后的结果。

anagram 英[ˈænəgræm] 美[ˈænəˌɡræm]
n.
由颠倒字母顺序而构成的字[短语];
[网络] 变位词; 颠倒顺序字; 字谜游戏;

Solutions

一开始的想法是，把两个字符串重新按照字母排序，再比较结果。
用的Arraylist和Collections.sort，效率感人，Runtime达到了114 ms，好可怕。

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;
        
        ArrayList<String> sa = new ArrayList<String>();
        for (int i = 0; i < s.length(); i++) {
            sa.add(s.substring(i, i + 1));
        }
        
        ArrayList<String> ta = new ArrayList<String>();
        for (int i = 0; i < t.length(); i++) {
            ta.add(t.substring(i, i + 1));
        }
        
        Collections.sort(sa);
        Collections.sort(ta);
        
        if (sa.equals(ta)) {
            return true;
        } else {
            return false;
        }
        
    }
}

然后去Discuss看了下，有和我思想相同的，但是效率高啊只有7ms！
人家用的Char[]和Arrays.sort，做人的差距怎么这么大呢（跪
其实一开始有想过转成Char[]再比较，但无知的我并不知道Arrays.sort的用法，于是就选择了熟悉的（牺牲效率）Arraylist。

public boolean isAnagram(String s, String t) { 
  char[] schar = s.toCharArray(); 
  char[] tchar = t.toCharArray(); 

  Arrays.sort(schar); 
  Arrays.sort(tchar); 

  // 不直接比较char[], 构成String后在比较
  String s1 = new String(schar); 
  String s2 = new String(tchar); 

  if(s1.equals(s2)) 
    return true; 
  else 
    return false;
}

然后还有只要三秒的方案
这种思想完全想不到啊/(ㄒoㄒ)/~~我等渣渣只有膜拜的份

public class Solution { 
  public boolean isAnagram(String s, String t) { 
    if (s.length() != t.length()) 
      return false; 
    
    char[] sChar = s.toCharArray(); 
    char[] tChar = t.toCharArray(); 

    int[] temp = new int[128];
    for (char c : sChar) { 
      temp[c]++; 
    } 
    for (char c : tChar) { 
      temp[c]--; 
      if (temp[c] < 0) 
        return false; 
     }
 
     return true; 
  }
}

TO DO

• Arraylist与数组效率处理
• Arrays.sort的用法