[LeetCode]Find All Anagrams in a String

niceforbear 發布于2019-08-16 10:26 / 3073人閱讀

摘要：解題思路，就是只順序不同但個數相同的字符串，那我們就可以利用的思想來比較每個字符串中字符出現的個數是否相等。

Find All Anagrams in a String
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".

1.解題思路

anagrams，就是只順序不同但個數相同的字符串，那我們就可以利用hashtable的思想來比較每個字符串中字符出現的個數是否相等。
對于兩個字符串我們分別準備數組(大小為256)來存儲每個字符出現的次數：
1) 對于p，我們遍歷，并在hp中記錄字符出現的次數；
2) 之后遍歷s,先把當前字符的個數+1，但是需要考慮當前index是否已經超過了p的長度，如果超過，則表示前面的字符已經不予考慮，所以要將index-plen的字符的個數-1；最后判斷兩個數組是否相等，如果相等，返回index-plen+1,即為開始的下標。

2.代碼

public class Solution {
    public List findAnagrams(String s, String p) {
        List res=new ArrayList();
        if(s.length()==0||s==null||p.length()==0||p==null) return res;
        int[] hs=new int[256];
        int[] hp=new int[256];
        int plen=p.length();
        for(int i=0;i=plen){
                hs[s.charAt(j-plen)]--;
            }
            if(Arrays.equals(hs,hp))
                res.add(j-plen+1);
        }
        return res;
    }
}

GPU云服務器云服務器 LeetCode_String FIND_IN_SET Anagrams All

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69799.html

leetcode438. Find All Anagrams in a String

摘要：題目要求思路和代碼這是一個簡單的雙指針問題，即左指針指向可以作為起點的子數組下標，右指針則不停向右移動，將更多的元素囊括進來，從而確保該左右指針內的元素是目標數組的一個兄弟子數組即每個字母的個數均相等左指針記錄每個字母出現的次數拷貝一個題目要求 Given a string s and a non-empty string p, find all the start indices ...

wangbinke 2019-08-16 17:50 評論0 收藏0
[LeetCode] 438. Find All Anagrams in a String [滑動窗

Problem Given a string s and a non-empty string p, find all the start indices of ps anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be...

muzhuyu 2019-08-19 11:18 評論0 收藏0
[LeetCode] Group Anagram

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 ...

kid143 2019-08-19 11:08 評論0 收藏0
leetcode49 Group Anagrams

摘要：同時使用方法將數組轉化為并利用的直接比較兩個字符串是否相等。通過這種方法效率值提高了不少。題目要求 Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat], Return: [ [ate, eat,tea], [nat,t...

sunsmell 2019-08-16 10:35 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0