Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/02/05 12:34)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串217/719 (看更多)

438. Find All Anagrams in a String 給你一個字串s和p，若s的某個子字串可以由p的字元排列後得到，返回s的子字串第一個字元的索引值。 Example : Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: s[0:2]="cba" 可以被p組合所以加入0 s[6:8]="bac" 可以被p組合所以加入6 思路： 1.首先，若p的長度大於s則必不存在解，所以可以直接返回。 2.因為p可以任意排列所以我們只關心他的字母數量，我們可以維護一個基於s的滑動窗口，每次加入一個元素，如果s的字母數量大於p就把最左邊的字母從窗口去除並更新窗口左邊界，直到窗口的字母數量小於等於目標數量。 3.如果窗口的大小剛好等於p那就表示有一個子字串滿足條件，將left加入結果集，當右邊的指標跑完s就可以得到解了。 Java Code： --------------------------------------- class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>(); if (s.length() < p.length()) { return res; } int[] target = new int[26]; for (char c : p.toCharArray()) { target[c - 'a']++; } int left = 0, right = 0; int [] window = new int[26]; while (right < s.length()) { char c = s.charAt(right); window[c - 'a']++; while (window[c - 'a'] > target[c - 'a']) { char first = s.charAt(left); window[first - 'a']--; left++; } if (right - left + 1 == p.length()) { res.add(left); } right++; } return res; } } --------------------------------------- -- https://i.imgur.com/PIoxddO.jpg