Problem
题目大意:在s中找出所有p的Anagrams。
https://leetcode.com/problems/find-all-anagrams-in-a-string/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".
Solution: HashTable + Sliding Window
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 35 ms class Solution { public: vector<int> findAnagrams(string s, string p) { int n = s.length(); int l = p.length(); vector<int> ans; vector<int> vp(26, 0); vector<int> vs(26, 0); for (char c : p) ++vp[c - 'a']; for (int i = 0; i < n; ++i) { if (i >= l) --vs[s[i - l] - 'a']; ++vs[s[i] - 'a']; if (vs == vp) ans.push_back(i + 1 - l); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment