编程开发练习题——Find All Anagrams in a String。最近又开始刷LeetCode了,很多之前做过的题目这次很快地做出来了。但是,今天遇到了Find All Anagrams in a String这题,又琢磨了好久,可能是没理解题目的精髓所在。
我的解特别low,使用HashMap,如下:
public ListfindAnagrams(String s, String p) { List list = new ArrayList<>(); if (s.length() < p.length()) return list; int sum = 0; HashMap map = new HashMap<>(); for (int i = 0; i < p.length(); i++) { map.put(p.charAt(i), map.getOrDefault(p.charAt(i), 0) - 1); } A: for (int i = 0; i < s.length(); i++) { if (sum == p.length()) { map.put(s.charAt(i - p.length()), map.getOrDefault(s.charAt(i - p.length()), 0) - 1); map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1); for (char key : map.keySet()) { if (map.get(key) != 0) continue A; } list.add(i - p.length() + 1); } else { map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1); sum++; if (sum == p.length()) { for (char key : map.keySet()) { if (map.get(key) != 0) continue A; } list.add(i - p.length() + 1); } } } return list; }
下面给出一个很棒的解答,利用滑动窗口的方法:
public ListfindAnagrams(String s, String p) { List list = new ArrayList<>(); if (s == null || s.length() == 0 || p == null || p.length() == 0) return list; int[] hash = new int[256]; //character hash //record each character in p to hash for (char c : p.toCharArray()) { hash[c]++; } //two points, initialize count to p's length int left = 0, right = 0, count = p.length(); while (right < s.length()) { //move right everytime, if the character exists in p's hash, decrease the count //current hash value >= 1 means the character is existing in p if (hash[s.charAt(right++)]-- >= 1) count--; //when the count is down to 0, means we found the right anagram //then add window's left to result list if (count == 0) list.add(left); //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window //++ to reset the hash because we kicked out the left //only increase the count if the character is in p //the count >= 0 indicate it was original in the hash, cuz it won't go below 0 if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++; } return list; }
下面这种利用滑动窗口Sliding Window的方法非常较巧妙。
首先统计字符串p的字符个数,然后用两个变量left和right表示滑动窗口的左右边界,用变量count表示字符串p中需要匹配的字符个数。
然后开始循环,如果右边界的字符已经在哈希表中了hash[s.charAt(right++)]-- >= 1,说明该字符在p中有出现,则count自减1,然后哈希表中该字符个数自减1,右边界自加1。
如果此时count减为0了,说明p中的字符都匹配上了,那么将此时左边界加入结果res中。
如果此时right和left的差为p的长度,说明此时应该去掉最左边的一个字符,我们看如果该字符在哈希表中的个数大于等于0,说明该字符是p中的字符。为什么呢,因为上面我们有让每个字符自减1,如果不是p中的字符,那么在哈希表中个数应该为0,自减1后就为-1,所以这样就知道该字符是否属于p。如果我们去掉了属于p的一个字符,count自增1。