1 两个字符串包含的字符是否完全相同
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.
可以用 HashMap 来映射字符与出现次数,然后比较两个字符串出现的字符数量是否相同。
由于本题的字符串只包含 26 个小写字符,因此可以使用长度为 26 的整型数组对字符串出现的字符进行统计,不再使用 HashMap。
public boolean isAnagram(String s, String t) {
int[] cnts = new int[26];
for (char c : s.toCharArray()) {
cnts[c - 'a']++;
}
for (char c : t.toCharArray()) {
cnts[c - 'a']--;
}
for (int cnt : cnts) {
if (cnt != 0) {
return false;
}
}
return true;
}
2 字符串同构
205. Isomorphic Strings (Easy)
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
记录一个字符上次出现的位置,如果两个字符串中的字符上次出现的位置一样,那么就属于同构。
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()); } }