p438

发表于 | 分类于 |

LeetCode p438 Find All Anagrams in a String 题解

1.题目：

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

题意：

输入字符串s,p。输出s中所有能用p中所有字母（可以任意调换位置）组成的子字符串。
输出符合要求的字符串首字母的下标。

2.解题思路:

见代码
用数组记录字母出现的次数。

3.代码

[title] [] [url] [link text]
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
 
public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<Integer>();
		int[] c = new int[26];
		for (char a : p.toCharArray()) {
			c[a - 'a']++;
		}
		int len = p.length();
		for (int i = 0; i + len <= s.length(); i++) {
			int[] x = new int[26];
			for (int j = 0; j < 26; j++) {
				x[j] = c[j];
			}
			for (int j = i; j < i + len; j++) {
				x[s.charAt(j) - 'a']--;
			}
			int flag = 0;
			for (int y : x) {
				if (y != 0) {
					flag = 1;
					break;
				}
			}
			if (flag == 0)
				ans.add(i);
		}
		return ans;
    }
}

4.一些总结：