Anagram of Strings

Posted on | In |

一个字符串$a$是另一个字符串$b$的anagram，需要满足以下两个条件：

  • $a$和$b$包含相同的字母表$\Sigma$。

  • 对于每一个$c\in \Sigma$，$a$和$b$中包含有相同个数的$c$。

LeetCode 242. Valid Anagram

如题所述，我们要判断两个字符串是否互为anagram。

直观解法

直观的思路：首先判断两个字符串长度是否相等，如果不相等，返回false。然后对两个数组分别建立HashMap<Character, Integer>，用来记录每个字母出现的次数。如果两个HashMap相等，返回true；如果不等，返回false。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    HashMap<Character, Integer> hms = new HashMap<>();
    HashMap<Character, Integer> hmt = new HashMap<>();
    for (char c : s.toCharArray()) {
        Integer temp = hms.get(c);
        hms.put(c, temp == null ? 1 : temp + 1);
    }
    for (char c : t.toCharArray()) {
        Integer temp = hmt.get(c);
        hmt.put(c, temp == null ? 1 : temp + 1);
    }
    return hms.equals(hmt);
}

改进的解法

优化这个代码有几种形式，一方面是如果字母表只包含英文字母，那么可以用int[]代替HashMap。另一方面，在建立第二个HashMap时可以判断当前c在第一个HashMap中的值是否为null，如果是，可以提前返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    HashMap<Character, Integer> hms = new HashMap<>();
    HashMap<Character, Integer> hmt = new HashMap<>();
    for (char c : s.toCharArray()) {
        Integer temp = hms.get(c);
        hms.put(c, temp == null ? 1 : temp + 1);
    }
    for (char c : t.toCharArray()) {
        if (hms.get(c) == null) {
            return false;
        }
        Integer temp = hmt.get(c);
        hmt.put(c, temp == null ? 1 : temp + 1);
    }
    return hms.equals(hmt);
}

LeetCode 438. Find All Anagrams in a String

如题所述，给定两个字符串s和p，我们要在s中找出所有是p的anagram的字串的开始下标。

使用滑动窗口方法可以在$O(n)$时间内得出结果。

快速解法

考虑字母为英文字母表，我们先使用int[]来解决这个题目。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new LinkedList<>();
    if (s == null || p == null || s.length() < p.length()) {
        return result;
    }
    int[] count = new int[26];
    int start = 0, end, len = p.length(), diff = len;
    for (int i = 0; i < len; i++) {
        char c = p.charAt(i);
        count[c - 'a']++;
    }
    for (end = 0; end < len; end++) {
        char c = s.charAt(end);
        count[c - 'a']--;
        if (count[c - 'a'] >= 0) {
            diff--;
        }
    }
    if (diff == 0) {
        result.add(0);
    }
    while (end < s.length()) {
        char c = s.charAt(start);
        count[c - 'a']++;
        if (count[c - 'a'] > 0) {
            diff++;
        }
        start++;
        c = s.charAt(end);
        count[c - 'a']--;
        if (count[c - 'a'] >= 0) {
            diff--;
        }
        end++;
        if (diff == 0) {
            result.add(start);
        }
    }
    return result;
}

代码看似复杂其实原理很简单。滑动窗口指的是我们维护两个指针，指针之间的距离相等，在这里等于p的长度，然后我们每次都同时向右移动这两个指针，并且判断这两个指针之间的s的子字符串是否是p的anagram。直观地考虑，如果$n$是两个字符串s和p的长度差的话，我们要移动$n$次，如果$m$是字符串p的长度，每次都要判断两个长度为$m$的字符串是否互为anagram。那么时间复杂度应该是$O(n\cdot m)$。然而，通过充分利用已有信息，我们可以做到在已知前一次判断的结果的情况下在$O(1)$时间内完成本次判断，从而在$O(n)$时间内解决问题。

那么代码可以被分为几个阶段。

阶段一：过滤输入

1
2
3
4
List<Integer> result = new LinkedList<>();
if (s == null || p == null || s.length() < p.length()) {
    return result;
}

过滤不合法输入，快速返回结果。如果s的长度比p的长度短，显然在s中是不存在是p的anagram的子串的。

阶段二：初始化

1
2
3
4
5
6
int[] count = new int[26];
int start = 0, end, len = p.length(), diff = len;
for (int i = 0; i < len; i++) {
    char c = p.charAt(i);
    count[c - 'a']++;
}

初始化count数组。将字符串p中的每个字符的数量记录在count中。

start和end是滑动窗口的左右两个指针，diff用来记录p和窗口内字串的相似程度，diff为0表示字串和p互为anagram。

阶段三：扩展窗口

1
2
3
4
5
6
7
8
9
10
for (end = 0; end < len; end++) {
    char c = s.charAt(end);
    count[c - 'a']--;
    if (count[c - 'a'] >= 0) {
        diff--;
    }
}
if (diff == 0) {
    result.add(0);
}

经过阶段二之后，滑动窗口的两个指针都指向0，窗口大小为0。所以我们要先将窗口扩展，直到大小等于p的长度。

在每次循环里，我们先将count中对应的元素自减。如果自减后该元素大小大于等于0，表示在自减前它大于0，也就是p和在窗口里的s字串同时包含这个字母。所以我们将diff自减。

在循环结束的时候滑动窗口的大小已经等于p的长度。这时如果diff为0，表示p与s从0开始的字串互为anagram。

阶段四：移动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (end < s.length()) {
    char c = s.charAt(start);
    count[c - 'a']++;
    if (count[c - 'a'] > 0) {
        diff++;
    }
    start++;
    c = s.charAt(end);
    count[c - 'a']--;
    if (count[c - 'a'] >= 0) {
        diff--;
    }
    end++;
    if (diff == 0) {
        result.add(start);
    }
}
return result;

在每个循环里，我们都会将start和end各自向右移动一位。同时为了能在$O(1)$的时间内判断是否互为anagram，我们在移动start和end时会对count和diff做相应的调整。

向右移动start表示start指向的元素即将退出窗口。在移动start前，先将start对应的count中的元素自增。如果自增后的数值大于0，表示在自增前该值不为负，对应地diff自增。

向右移动end表示end指向的元素即将进入窗口。对应地我们调整count和diff。

在每次循环后如果diff为0表示我们找到了一个合法结果，加入到结果List中。

  • diff是能够在$O(1)$时间内完成判断的关键。指针移动修改count，再通过count的变化维护diff，从而保证每次指针移动都可以在$O(1)$时间内完成判断。

使用HashMap的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new LinkedList<>();
    if (s == null || p == null || s.length() < p.length()) {
        return result;
    }
    HashMap<Character, Integer> count = new HashMap<>();
    int start = 0, end, len = p.length(), diff = len;
    for (int i = 0; i < len; i++) {
        Character c = p.charAt(i);
        count.put(c, count.getOrDefault(c, 0) + 1);
    }
    for (end = 0; end < len; end++) {
        Character c = s.charAt(end);
        count.put(c, count.getOrDefault(c, 0) - 1);
        if (count.getOrDefault(c, -1) >= 0) {
            diff--;
        }
    }
    if (diff == 0) {
        result.add(0);
    }
    while (end < s.length()) {
        Character c = s.charAt(start);
        count.put(c, count.get(c) + 1);
        if (count.get(c) > 0) {
            diff++;
        }
        start++;
        c = s.charAt(end);
        count.put(c, count.getOrDefault(c, 0) - 1);
        if (count.get(c) >= 0) {
            diff--;
        }
        end++;
        if (diff == 0) {
            result.add(start);
        }
    }
    return result;
}

仅仅将int[]变成HashMap<Character, Integer>，其他相同。

LeetCode 49. Group Anagrams

如题所述，要把互为Anagram的字符串划为一组。

解法一

没有什么太快的方法，还是Hash的思想。对于每一个字符串str，抽取特征，将特征相同的strhash到一组，组织结果输出即可。

互为Anagram的字符串特征为每个字符串在各个字符上的分量相同，我们可以将字符串在各个字符上的分量组织成字符串，然后作为HashMap的key进行hash，组成列表即可。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> result = new LinkedList<>();
    if (strs.length == 0) {
        return result;
    }
    HashMap<String, List<String>> hm = new HashMap<>();
    for (int i = 0; i < strs.length; i++) {
        StringBuilder sb = new StringBuilder();
        char[] chars = strs[i].toCharArray();
        int[] count = new int[26];
        for (int j = 0; j < chars.length; j++) {
            count[chars[j] - 'a']++;
        }
        for (int j = 0; j < 26; j++) {
            sb.append('#').append(count[j]);
        }
        if (hm.containsKey(sb.toString())) {
            hm.get(sb.toString()).add(strs[i]);
        } else {
            List<String> list = new LinkedList<>();
            list.add(strs[i]);
            result.add(list);
            hm.put(sb.toString(), list);
        }
    }
    return result;
}

改进解法

解法一中抽取特征时反复构造字符串性能很差。考虑将每个字符对应一个质数，将字符串str的特征抽取为str中各个字符c对应质数的乘积，并将乘积作为特征进行hash。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> result = new LinkedList<>();
    if (strs.length == 0) {
        return result;
    }
    int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };
    HashMap<Integer, List<String>> hm = new HashMap<>();
    for (int i = 0; i < strs.length; i++) {
        char[] charList = strs[i].toCharArray();
        int feature = 1;
        for (char c : charList) {
            feature *= primes[c - 'a'];
        }
        if (hm.containsKey(feature)) {
            hm.get(feature).add(strs[i]);
        } else {
            List<String> strList = new LinkedList<>();
            strList.add(strs[i]);
            result.add(strList);
            hm.put(feature, strList);
        }
    }
    return result;
}

这个答案比99%的提交要快。看来记住一个长度26的质数序列还是有必要的。

相关LeetCode 249. Group Shifted Strings

思路还是一样的：提取特征，依据特征hash并分组。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<String>> groupStrings(String[] strings) {
    List<List<String>> result = new LinkedList<>();
    if (strings.length == 0) {
        return result;
    }
    HashMap<String, List<String>> hm = new HashMap<>();
    for (int i = 0; i < strings.length; i++) {
        StringBuilder sb = new StringBuilder();
        char[] charList = strings[i].toCharArray();
        char first = charList[0];
        for (char c : charList) {
            sb.append('#').append((c - first + 26) % 26);
        }
        if (hm.containsKey(sb.toString())) {
            hm.get(sb.toString()).add(strings[i]);
        } else {
            List<String> tempList = new LinkedList<>();
            tempList.add(strings[i]);
            result.add(tempList);
            hm.put(sb.toString(), tempList);
        }
    }
    return result;
}