Problem
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".
class Solution { public Listsliding windowfindAnagrams(String s, String p) { List res = new ArrayList<>(); if (s == null || p == null || s.length() < p.length()) return res; for (int i = 0; i <= s.length()-p.length(); i++) { if (isAnagram(s.substring(i, i+p.length()), p)) res.add(i); } return res; } private boolean isAnagram(String a, String b) { int[] dict = new int[256]; for (char ch: a.toCharArray()) { dict[ch]++; } for (char ch: b.toCharArray()) { dict[ch]--; if (dict[ch] < 0) return false; } return true; } }
class Solution { public Listupdate 2018-10 with commentsfindAnagrams(String s, String p) { List res = new LinkedList<>(); if (s.length() == 0 || p.length() == 0 || s.length() < p.length()) return res; int[] dict = new int[26]; for (char ch: p.toCharArray()) { dict[ch-"a"]++; } int start = 0, end = p.length(), diff = p.length(); for (int i = 0; i < p.length(); i++) { int index = s.charAt(i)-"a"; dict[index]--; if (dict[index] >= 0) diff--; } if (diff == 0) res.add(0); while (end < s.length()) { int index = s.charAt(start)-"a"; if (dict[index] >= 0) diff++; dict[index]++; start++; index = s.charAt(end)-"a"; dict[index]--; if (dict[index] >= 0) diff--; end++; if (diff == 0) res.add(start); } return res; } }
class Solution { public ListfindAnagrams(String s, String p) { List res = new LinkedList<>(); if (s.length() == 0 || p.length() == 0 || s.length() < p.length()) return res; int[] dict = new int[26]; for (char ch: p.toCharArray()) { dict[ch-"a"]++; } int start = 0, end = p.length(), diff = p.length(); for (int i = 0; i < p.length(); i++) { int index = s.charAt(i)-"a"; dict[index]--; if (dict[index] >= 0) diff--; } if (diff == 0) res.add(0); while (end < s.length()) { //will release the s.charAt(start), //so if >= 0 in map, that means we released one char in anagram, so increase diff by 1, //else it"s not in anagram of p, continue //after release, increase it back in map //shift start int index = s.charAt(start)-"a"; if (dict[index] >= 0) diff++; dict[index]++; start++; //will store the s.charAt(end), //so first decrease in map, //if still >= 0, that means we saved one char that is in anagram p, so reduce diff by 1 //else it"s not in anagram of p, continue //shift end index = s.charAt(end)-"a"; dict[index]--; if (dict[index] >= 0) diff--; end++; //if diff became 0 at the end of this iteration, add index start to result if (diff == 0) res.add(start); } return res; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/77382.html
摘要:題目要求思路和代碼這是一個簡單的雙指針問題,即左指針指向可以作為起點的子數組下標,右指針則不停向右移動,將更多的元素囊括進來,從而確保該左右指針內的元素是目標數組的一個兄弟子數組即每個字母的個數均相等左指針記錄每個字母出現的次數拷貝一個 題目要求 Given a string s and a non-empty string p, find all the start indices ...
摘要:解題思路,就是只順序不同但個數相同的字符串,那我們就可以利用的思想來比較每個字符串中字符出現的個數是否相等。 Find All Anagrams in a StringGiven a string s and a non-empty string p, find all the start indices of ps anagrams in s. Strings consists of...
摘要:在線網站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目,語言 JavaScript。 在線網站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...
摘要:月下半旬攻略道題,目前已攻略題。目前簡單難度攻略已經到題,所以后面會調整自己,在刷算法與數據結構的同時,攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區別...
Problem Given an array of strings, group anagrams together. Example: Input: [eat, tea, tan, ate, nat, bat], Output: [ [ate,eat,tea], [nat,tan], [bat] ] Note: All inputs will be in lowercase.The ...
閱讀 2572·2021-09-23 11:21
閱讀 1882·2021-09-22 15:15
閱讀 970·2021-09-10 11:27
閱讀 3440·2019-08-30 15:54
閱讀 653·2019-08-30 15:52
閱讀 1335·2019-08-30 15:44
閱讀 2349·2019-08-29 15:06
閱讀 2972·2019-08-28 18:21