Welcome to Subscribe On Youtube
-
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; } } } ############ class Solution { public List<Integer> findAnagrams(String s, String p) { int[] counter = new int[26]; for (char c : p.toCharArray()) { ++counter[c - 'a']; } List<Integer> ans = new ArrayList<>(); int left = 0, right = 0; int[] t = new int[26]; while (right < s.length()) { int i = s.charAt(right) - 'a'; ++t[i]; while (t[i] > counter[i]) { --t[s.charAt(left) - 'a']; ++left; } if (right - left + 1 == p.length()) { ans.add(left); } ++right; } return ans; } }
-
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: counter = Counter(p) ans = [] left = right = 0 t = Counter() while right < len(s): t[s[right]] += 1 while t[s[right]] > counter[s[right]]: t[s[left]] -= 1 left += 1 if right - left + 1 == len(p): ans.append(left) right += 1 return ans ############ 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
-
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> counter(26); for (char c : p) ++counter[c - 'a']; vector<int> ans; int left = 0, right = 0; vector<int> t(26); while (right < s.size()) { int i = s[right] - 'a'; ++t[i]; while (t[i] > counter[i]) { --t[s[left] - 'a']; ++left; } if (right - left + 1 == p.size()) ans.push_back(left); ++right; } return ans; } };
-
func findAnagrams(s string, p string) []int { counter := make([]int, 26) for _, c := range p { counter[c-'a']++ } var ans []int left, right := 0, 0 t := make([]int, 26) for right < len(s) { i := s[right] - 'a' t[i]++ for t[i] > counter[i] { t[s[left]-'a']-- left++ } if right-left+1 == len(p) { ans = append(ans, left) } right++ } return ans }
-
function findAnagrams(s: string, p: string): number[] { let n = s.length, m = p.length; let cnt = new Array(26).fill(0); let ans = []; for (let i = 0; i < m; i++) { cnt[p.charCodeAt(i) - 97]--; cnt[s.charCodeAt(i) - 97]++; } if (cnt.every(v => v == 0)) { ans.push(0); } for (let i = m; i < n; i++) { cnt[s.charCodeAt(i) - 97]++; cnt[s.charCodeAt(i - m) - 97]--; if (cnt.every(v => v == 0)) { ans.push(i - m + 1); } } return ans; }
-
impl Solution { pub fn find_anagrams(s: String, p: String) -> Vec<i32> { let (s, p) = (s.as_bytes(), p.as_bytes()); let (m, n) = (s.len(), p.len()); let mut res = vec![]; if n > m { return res; } let mut counter = [0; 26]; for i in 0..n { counter[(p[i] - b'a') as usize] += 1; counter[(s[i] - b'a') as usize] -= 1; } for i in n..m { if counter.iter().all(|&v| v == 0) { res.push((i - n) as i32); } counter[(s[i] - b'a') as usize] -= 1; counter[(s[i - n] - b'a') as usize] += 1; } if counter.iter().all(|&v| v == 0) { res.push((m - n) as i32); } res } }
-
public class Solution { public IList<int> FindAnagrams(string s, string p) { int m = s.Length, n = p.Length; IList<int> ans = new List<int>(); if (m < n) { return ans; } int[] cnt1 = new int[26]; int[] cnt2 = new int[26]; for (int i = 0; i < n; ++i) { ++cnt1[p[i] - 'a']; } for (int i = 0, j = 0; i < m; ++i) { int k = s[i] - 'a'; ++cnt2[k]; while (cnt2[k] > cnt1[k]) { --cnt2[s[j++] - 'a']; } if (i - j + 1 == n) { ans.Add(j); } } return ans; } }
-
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; } } ############ class Solution { public List<Integer> findAnagrams(String s, String p) { int[] counter = new int[26]; for (char c : p.toCharArray()) { ++counter[c - 'a']; } List<Integer> ans = new ArrayList<>(); int left = 0, right = 0; int[] t = new int[26]; while (right < s.length()) { int i = s.charAt(right) - 'a'; ++t[i]; while (t[i] > counter[i]) { --t[s.charAt(left) - 'a']; ++left; } if (right - left + 1 == p.length()) { ans.add(left); } ++right; } return ans; } }
-
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: counter = Counter(p) ans = [] left = right = 0 t = Counter() while right < len(s): t[s[right]] += 1 while t[s[right]] > counter[s[right]]: t[s[left]] -= 1 left += 1 if right - left + 1 == len(p): ans.append(left) right += 1 return ans ############ 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
-
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> counter(26); for (char c : p) ++counter[c - 'a']; vector<int> ans; int left = 0, right = 0; vector<int> t(26); while (right < s.size()) { int i = s[right] - 'a'; ++t[i]; while (t[i] > counter[i]) { --t[s[left] - 'a']; ++left; } if (right - left + 1 == p.size()) ans.push_back(left); ++right; } return ans; } };
-
func findAnagrams(s string, p string) []int { counter := make([]int, 26) for _, c := range p { counter[c-'a']++ } var ans []int left, right := 0, 0 t := make([]int, 26) for right < len(s) { i := s[right] - 'a' t[i]++ for t[i] > counter[i] { t[s[left]-'a']-- left++ } if right-left+1 == len(p) { ans = append(ans, left) } right++ } return ans }
-
function findAnagrams(s: string, p: string): number[] { let n = s.length, m = p.length; let cnt = new Array(26).fill(0); let ans = []; for (let i = 0; i < m; i++) { cnt[p.charCodeAt(i) - 97]--; cnt[s.charCodeAt(i) - 97]++; } if (cnt.every(v => v == 0)) { ans.push(0); } for (let i = m; i < n; i++) { cnt[s.charCodeAt(i) - 97]++; cnt[s.charCodeAt(i - m) - 97]--; if (cnt.every(v => v == 0)) { ans.push(i - m + 1); } } return ans; }
-
impl Solution { pub fn find_anagrams(s: String, p: String) -> Vec<i32> { let (s, p) = (s.as_bytes(), p.as_bytes()); let (m, n) = (s.len(), p.len()); let mut res = vec![]; if n > m { return res; } let mut counter = [0; 26]; for i in 0..n { counter[(p[i] - b'a') as usize] += 1; counter[(s[i] - b'a') as usize] -= 1; } for i in n..m { if counter.iter().all(|&v| v == 0) { res.push((i - n) as i32); } counter[(s[i] - b'a') as usize] -= 1; counter[(s[i - n] - b'a') as usize] += 1; } if counter.iter().all(|&v| v == 0) { res.push((m - n) as i32); } res } }
-
public class Solution { public IList<int> FindAnagrams(string s, string p) { int m = s.Length, n = p.Length; IList<int> ans = new List<int>(); if (m < n) { return ans; } int[] cnt1 = new int[26]; int[] cnt2 = new int[26]; for (int i = 0; i < n; ++i) { ++cnt1[p[i] - 'a']; } for (int i = 0, j = 0; i < m; ++i) { int k = s[i] - 'a'; ++cnt2[k]; while (cnt2[k] > cnt1[k]) { --cnt2[s[j++] - 'a']; } if (i - j + 1 == n) { ans.Add(j); } } return ans; } }