Java
-
import java.util.ArrayList; import java.util.List; /** 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". */ public class Find_All_Anagrams_in_a_String { public class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>(); if (p == null || s == null || s.length() < p.length()) return res; int m = s.length(), n = p.length(); for (int i = 0; i < m-n+1; i++) { String cur = s.substring(i, i+n); if (helper(cur, p)) { res.add(i); } } return res; } public boolean helper(String a, String b) { if (a == null || b == null || a.length() != b.length()) { return false; } int[] dict = new int[26]; // 2*logN is better than sorting 2*NlogN for (int i = 0; i < a.length(); i++) { char ch = a.charAt(i); dict[ch-'a']++; } for (int i = 0; i < b.length(); i++) { char ch = b.charAt(i); dict[ch-'a']--; if (dict[ch-'a'] < 0) return false; } return true; } } }
-
Todo
-
from collections import Counter class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ sCount = Counter(s[:len(p) - 1]) pCount = Counter(p) ans = [] for i in range(len(p) - 1, len(s)): sCount[s[i]] += 1 if sCount == pCount: ans.append(i - len(p) + 1) sCount[s[i - len(p) + 1]] -= 1 if sCount[s[i - len(p) + 1]] == 0: del sCount[s[i - len(p) + 1]] return ans
Java
-
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> indices = new ArrayList<Integer>(); if (s == null || p == null || s.length() < p.length()) return indices; int sLength = s.length(); int pLength = p.length(); int[] sCount = new int[26]; int[] pCount = new int[26]; for (int i = 0; i < pLength; i++) { sCount[s.charAt(i) - 'a']++; pCount[p.charAt(i) - 'a']++; } if (match(sCount, pCount)) indices.add(0); for (int i = pLength; i < sLength; i++) { char prevC = s.charAt(i - pLength), curC = s.charAt(i); sCount[prevC - 'a']--; sCount[curC - 'a']++; if (match(sCount, pCount)) indices.add(i - pLength + 1); } return indices; } public boolean match(int[] sCount, int[] pCount) { for (int i = 0; i < 26; i++) { if (sCount[i] != pCount[i]) return false; } return true; } }
-
Todo
-
from collections import Counter class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ sCount = Counter(s[:len(p) - 1]) pCount = Counter(p) ans = [] for i in range(len(p) - 1, len(s)): sCount[s[i]] += 1 if sCount == pCount: ans.append(i - len(p) + 1) sCount[s[i - len(p) + 1]] -= 1 if sCount[s[i - len(p) + 1]] == 0: del sCount[s[i - len(p) + 1]] return ans