1 两个字符串包含的字符是否完全相同

s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.
可以用 HashMap 来映射字符与出现次数，然后比较两个字符串出现的字符数量是否相同。
由于本题的字符串只包含 26 个小写字符，因此可以使用长度为 26 的整型数组对字符串出现的字符进行统计，不再使用 HashMap。

  1. public boolean isAnagram(String s, String t) {
  2.     int[] cnts = new int[26];
  3.     for (char c : s.toCharArray()) {
  4.         cnts[c - 'a']++;
  5.     }
  6.     for (char c : t.toCharArray()) {
  7.         cnts[c - 'a']--;
  8.     }
  9.     for (int cnt : cnts) {
  10.         if (cnt != 0) {
  11.             return false;
  12.         }
  13.     }
  14.     return true;
  15. }

2 字符串同构

  1. 205. Isomorphic Strings (Easy)
  2. Given "egg", "add", return true.
  3. Given "foo", "bar", return false.
  4. Given "paper", "title", return true.
  5. 记录一个字符上次出现的位置，如果两个字符串中的字符上次出现的位置一样，那么就属于同构。
public boolean isIsomorphic(String s, String t) {
    int[] preIndexOfS = new int[256];
    int[] preIndexOfT = new int[256];
    for (int i = 0; i < s.length(); i++) {
        char sc = s.charAt(i), tc = t.charAt(i);
        if (preIndexOfS[sc] != preIndexOfT[tc]) {
            return false;
        }
        preIndexOfS[sc] = i + 1;
        preIndexOfT[tc] = i + 1;
    }
    return true;
}

3 回文子字符串个数

647. Palindromic Substrings (Medium)
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
从字符串的某一位开始，尝试着去扩展子字符串。

private int cnt = 0;

public int countSubstrings(String s) {
    for (int i = 0; i < s.length(); i++) {
        extendSubstrings(s, i, i);     // 奇数长度
        extendSubstrings(s, i, i + 1); // 偶数长度
    }
    return cnt;
}

private void extendSubstrings(String s, int start, int end) {
    while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
        start--;
        end++;
        cnt++;
    }
}

3 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

  • hashmap, 用排好序的单词为key
  • 如果单词的key不存在，用排好序的单词为key， 单词为value

  • 存在， put单词进key映射的链表上， 

    class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
      if (strs.length == 0) return new ArrayList();
      Map<String, List> ans = new HashMap<String, List>();
      for (String s : strs){
          char[] ca = s.toCharArray();
          Arrays.sort(ca);
          String key = String.valueOf(ca);
          if (!ans.containsKey(key)) ans.put(key, new ArrayList());
          ans.get(key).add(s);
      }
      return new ArrayList(ans.values());

  }
}