438 Find All Anagrams in a Strin
2019-08-09 本文已影响0人
烟雨醉尘缘
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：
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".
解释下题目：
判断一个字符串里anagram的个数。
1. 老老实实判断
实际耗时：856ms
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i <= s.length() - p.length(); i++) {
String tmp = s.substring(i, i + p.length());
if (isAnagram(tmp, p)) {
res.add(i);
}
}
return res;
}
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
//长度都不相同还怎么可能是
return false;
}
int[] arr = new int[26];
for (int i = 0; i < s.length(); i++) {
arr[s.charAt(i) - 'a']++;
arr[t.charAt(i) - 'a']--;
}
for (int i = 0; i < s.length(); i++) {
if (arr[s.charAt(i) - 'a'] != 0) {
return false;
}
}
return true;
}
思路不说了，简单粗暴。
时间复杂度O(n*m) n为s的长度，m为p的长度。
空间复杂度O(1)
2. 滑动窗口
实际耗时：8ms
public List<Integer> findAnagrams2(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s == null || s.length() == 0 || p == null || p.length() == 0) return res;
int[] table = new int[256];
for (char c : p.toCharArray()) {
table[c]++;
}
int left = 0, right = 0, count = 0;
while (right < s.length()) {
if (table[s.charAt(right)] > 0) {
count++;
}
table[s.charAt(right)]--;
right++;
if (count == p.length()) {
res.add(left);
}
if (right - left == p.length()) {
if (table[s.charAt(left)] >= 0) {
count--;
}
table[s.charAt(left)]++;
left++;
}
}
return res;
}
其实一说滑动窗口就差不多都明白了，省力在如果p很长的情况下，有一大部分其实是可以省略判断的，有点像动态规划，所以那么省。需要注意的是，滑动窗口往右边移动的时候，如果划入窗口的那个字母不存在于table中，还是需要减一的，也就是table中的元素可能是负的，这一点我当时没想通，导致左边滑入的时候count无法做判断，想了半天。
