FindAllAnagramsInAString [source code]
public class FindAllAnagramsInAString {
static
/******************************************************************************/
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
char[] chs = s.toCharArray(), chp = p.toCharArray();
List<Integer> res = new ArrayList<>();
int lenS = chs.length, lenP = chp.length;
for (int i = 0; i < lenS; i++) {
if (isAnagram(chs, chp, i)) {
res.add(i);
}
}
return res;
}
public boolean isAnagram(char[] chs, char[] chp, int start) {
int lenS = chs.length, lenP = chp.length;
if (start + lenP > lenS) return false;
int[] counts = new int[26];
for (int i = 0; i < lenP; i++) {
counts[chs[i + start] - 'a']++;
counts[chp[i] - 'a']--;
}
for (int i = 0; i < 26; i++) if (counts[i] > 0) return false;
return true;
}
}
/******************************************************************************/
public static void main(String[] args) {
FindAllAnagramsInAString.Solution tester = new FindAllAnagramsInAString.Solution();
String[] inputs = {
"cbaebabacd", "abc",
"abab", "ab",
"abdkaabacdkajfl", "babc",
"abdkaabbacdkajfl", "babc",
};
for (int i = 0; i < inputs.length / 2; i++) {
String s = inputs[2 * i];
String p = inputs[1 + 2 * i];
System.out.println(s + " VS " + p + " -> " + tester.findAnagrams(s, p));
}
}
}
这个题目的暴力算法还是很简单的, 直接就是挨个找就行了, 最后的复杂度是O(M*(N^2)).
这个题目要考虑的一点是两个 string 如果有 duplicate 怎么办? 有 duplicate 好像做起来麻烦不少;
这个题目一开始想的太复杂了, 其实思路非常简单. 之前那个想复杂了但是不对的代码扔在ver2了;
先做一个粗糙解, 做一个 i 需要 backup 的解; 后面想想能不能类似 KMP 那样跳子;
我这里判断每个 window 里面的是 anagram 的方法其实是直接用 char 值加起来求和相等就可以, 求和的作用就是为了消除顺序的影响. 不过不能直接求和, 因为比如0 1 2 3, 那么0 3的和跟1 2的和就是相等的. 所以我的做法是先平方再求和. 不过没有想到居然有人专门预料到了有人会这么写, 直接专门搞了一个 case, break 这个算法, 这个 case 的核心点就是"buq" 和"ncw" 两个的平方求和是相等的. 我就干脆换成了三次方. 不过感觉过一段时间还是会有蛋疼的人加 case 来 break 这个.
要么更好的方法是换一个更隐秘的算法来计算这个和, 要么就是换一个思路. 我认为只要保证 window 里面两个 string 的 constituents 相同, 好像就可以了;
果然, 三次方还是有问题, 这帮比故意一个 case, 很长的一个 string, 全都是'a', 让你超时;
那我试试+1之后平方; //+1好像还是跑不过 buq 这个 case; 算了, 直接 count 算了. count 也是O(N) 的速度, 何苦呢;
for (int i = 0; i < lenP; i++) {
sum1 += Math.pow(chs[start + i] + 1, 2);
sum2 += Math.pow(chp[i] + 1, 2);
}
这个是当时计算的代码, 留个存根;
吭哧吭哧做完了, 结果最后的速度惨不忍睹, 不知道哪里出问题了: 710ms (10%).
Problem Description
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".
Difficulty:Easy
Total Accepted:33.2K
Total Submissions:99K
Contributor: Stomach_ache
Companies
amazon
Related Topics
hash table
Similar Questions
Valid Anagram Permutation in String