[Leetcode] Substring with Concatenation of All Wor

adie 发布于2019-08-14 12:46 / 338人阅读

摘要：每次搜索中，我们通过哈希表维护一个窗口，比如中，我们先拿出。如果都不在数组中，那说明根本不能拼进去，则哈希表全部清零，从下一个词开始重新匹配。

Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).

哈希表计数法 复杂度

时间 O(NK) 空间 O(M)

思路

由于数组中所有单词的长度都是一样的，我们可以像Longest Substring with At Most Two Distinct Characters中一样，把每个词当作一个字母来看待，但是要遍历K次，K是单词的长度，因为我们要分别统计从下标0开头，从下标1开头。。。直到下标K-1开头的字符串。举例来说foobarfoo，给定数组是[foo, bar]，那我们要对foo|bar|foo搜索一次，对oob|arf|oo搜索一次，对oba|rfo|o搜索一次，我们不用再对bar|foo搜索，因为其已经包含在第一种里面了。每次搜索中，我们通过哈希表维护一个窗口，比如foo|bar|foo中，我们先拿出foo。如果foo都不在数组中，那说明根本不能拼进去，则哈希表全部清零，从下一个词开始重新匹配。但是foo是在数组中的，所以给当前搜索的哈希表计数器加上1，如果发现当前搜索中foo出现的次数已经比给定数组中foo出现的次数多了，我们就要把上一次出现foo之前的所有词都从窗口中去掉，如果没有更多，则看下一个词bar，不过在这之前，我们还要看看窗口中有多少个词了，如果词的个数等于数组中词的个数，说明我们找到了一个结果。

注意

先判断输入是否为空，为空直接返回空结果

代码

public class Solution {
    public List findSubstring(String s, String[] words) {
        List res = new LinkedList();
        if(words == null || words.length == 0 || s == null || s.equals("")) return res;
        HashMap freq = new HashMap();
        // 统计数组中每个词出现的次数，放入哈希表中待用
        for(String word : words){
            freq.put(word, freq.containsKey(word) ? freq.get(word) + 1 : 1);
        }
        // 得到每个词的长度
        int len = words[0].length();
        // 错开位来统计
        for(int i = 0; i < len; i++){
            // 建一个新的哈希表，记录本轮搜索中窗口内单词出现次数
            HashMap currFreq = new HashMap();
            // start是窗口的开始，count表明窗口内有多少词
            int start = i, count = 0;
            for(int j = i; j <= s.length() - len; j += len){
                String sub = s.substring(j, j + len);
                // 看下一个词是否是给定数组中的
                if(freq.containsKey(sub)){
                    // 窗口中单词出现次数加1
                    currFreq.put(sub, currFreq.containsKey(sub) ? currFreq.get(sub) + 1 : 1);
                    count++;
                    // 如果该单词出现次数已经超过给定数组中的次数了，说明多来了一个该单词，所以要把窗口中该单词上次出现的位置及之前所有单词给去掉
                    while(currFreq.get(sub) > freq.get(sub)){
                        String leftMost = s.substring(start, start + len);
                        currFreq.put(leftMost, currFreq.get(leftMost) - 1);
                        start = start + len;
                        count--;
                    }
                    // 如果窗口内单词数和总单词数一样，则找到结果
                    if(count == words.length){
                        String leftMost = s.substring(start, start + len);
                        currFreq.put(leftMost, currFreq.get(leftMost) - 1);
                        res.add(start);
                        start = start + len;
                        count--;
                    }
                // 如果截出来的单词都不在数组中，前功尽弃，重新开始
                } else {
                    currFreq.clear();
                    start = j + len;
                    count = 0;
                }
            }
        }
        return res;
    }
}

GPU云服务器云服务器 Concatenation LeetCode Substring LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64700.html

leetcode30 Substring with Concatenation of All Wor

摘要：同时利用来存储当前结果值所在的起始下标。然而，一旦出现重复值后，例如输入的为，则无法判断当前重复值是否应当在结果集中。如果中的元素都被清空，则代表该子数组符合要求，即将起始下标添加进入结果集。利用左右指针来限定最小子数组的范围，即窗口大小。题目要求 You are given a string, s, and a list of words, words, that are all ...

Y3G 2019-08-14 18:35 评论0 收藏0
[leetcode] Minimum Window Substring

摘要：使用而不是因为我们需要的是最值，中间值我们不在乎，所以一次收敛到最小。下面来三个需要查重并且记录上次出现的位置，选择以为例，走到用做检查，发现出现过，把移到的下一个。是上个题目的简易版，或者特殊版。这里聊一聊解一类问题，就是满足某一条件的substring最值问题。最开始我们以Minimum Window Substring为例，并整理总结leetcode里所有类似题目的通解。 Gi...

Pines_Cheng 2019-08-14 17:17 评论0 收藏0
[LeetCode] 336. Palindrome Pairs

Problem Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome. Example 1: Inpu...

lentoo 2019-08-16 13:45 评论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