[LintCode] Substring Anagrams

andong777 發布于2019-08-15 13:24 / 869人閱讀

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 40,000.

The order of output does not matter.

Example

Given s = "cbaebabacd" p = "abc"

return [0, 6]

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

Solution

public class Solution {
    public List findAnagrams(String s, String p) {
    
        List res = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) return res;
        
        //since it"s all lowercase English letters
        int[] sum = new int[26];
        for (char ch: p.toCharArray()) {
            sum[ch-"a"]++;
        }
        
        //build a sliding window
        int start = 0, end = 0, matched = 0;
        while (end < s.length()) {
            int index = s.charAt(end) - "a";
            if (sum[index] > 0) {
                matched++;
            } 
            sum[index]--;
            end++;
            //once the number of matched equals to p.length(), add the start index to result
            if (matched == p.length()) {
                res.add(start);
            }
            
            //move the window forward, restore `sum`
            if (end-start == p.length()) {
                if (sum[s.charAt(start)-"a"] >= 0) {
                    matched--;
                }
                sum[s.charAt(start)-"a"]++;
                start++;
            }
        }
        
        return res;
    }
}

云服務器 GPU云服務器 Anagrams LintCode LintCode134_LRU Substring

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

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

[LintCode] Anagrams

摘要：對變形詞的查找和歸類，可以將自然排序的詞根和所有同根變形詞成對存入哈希表里。然后，返回里大于的字符串數組，再存入結果數組。注意并不是的結構，而是和數組相同的，所以存到一定要用方法。有幾行容易出錯的語句，可以注意一下 Problem Given an array of strings, return all groups of strings that are anagrams. Not...

GitChat 2019-08-14 15:22 評論0 收藏0
[LintCode/LeetCode] Two Strings are Anagrams/Valid

摘要：建立一個長度為的數組，統計所有個字符在出現的次數，然后減去這些字符在中出現的次數。否則，循環結束，說明所有字符在和中出現的次數一致，返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....

vslam 2019-08-14 15:22 評論0 收藏0
[LeetCode]Find All Anagrams in a String

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

niceforbear 2019-08-16 10:26 評論0 收藏0
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