LeetCode - 30. Substring with Concatenation of All Words

简介: 30. Substring with Concatenation of All Words  Problem's Link  ---------------------------------------------------------------------------...

30. Substring with Concatenation of All Words 

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给你一个字符串s,和一个字符串集合words,找出s中words所有单词连续出现的起始下标.

analyse:

思路:窗口滑动算法.

枚举所有长度为words[0].length()的子串,然后使用窗口滑动算法来统计.

Trick:集合words是一个可重集,当连续出现的单词书大于words中的时,需要回退删除开头部分的单词,注意细节.

Time complexity: O(N)

 

view code

class Solution
{
public :

    vector < int > findSubstring( string s , vector < string > & words)
    {
        vector < int > ans;
        int n = s . size (), cnt = words . size();
        if (n <= 0 || cnt <= 0) return ans;

        // init word occurence
        unordered_map < string , int > dict;
        for ( int i = 0; i < cnt; ++ i)   //统计每个单词出现的次数
            dict [ words [ i ]] ++;

        // travel all sub string combinations
        int wl = words [ 0 ]. size();
        for ( int i = 0; i < wl; ++ i)
        {
            int left = i , continueWords = 0;
            unordered_map < string , int > tdict;
            for ( int j = i; j <= n - wl; j += wl)
            {
                string str = s . substr( j , wl);
                // a valid word, accumulate results
                if ( dict . count( str))
                {
                    tdict [ str ] ++;
                    if ( tdict [ str ] <= dict [ str ])
                        continueWords ++;
                    else
                    {
                        // a more word, advance the window left side possiablly
                        while ( tdict [ str ] > dict [ str ])
                        {
                            string str1 = s . substr( left , wl);
                            tdict [ str1 ] --;
                            if ( tdict [ str1 ] < dict [ str1 ]) continueWords --;
                            left += wl;
                        }
                    }

                    // come to a result
                    if ( continueWords == cnt)
                    {
                        ans . push_back( left);
                        // advance one word
                        tdict [s . substr( left , wl )] --;
                        continueWords --;
                        left += wl;
                    }
                }
                // not a valid word, reset all vars
                else
                {
                    tdict . clear();
                    continueWords = 0;
                    left = j + wl;
                }
            }
        }
        return ans;
    }
};
目录
相关文章
LeetCode contest 187 1437. 是否所有 1 都至少相隔 k 个元素 Check If All 1's Are at Least Length K Places Away
LeetCode contest 187 1437. 是否所有 1 都至少相隔 k 个元素 Check If All 1's Are at Least Length K Places Away
|
iOS开发
LeetCode All in One 题目讲解汇总(持续更新中...)
终于将LeetCode的免费题刷完了,真是漫长的第一遍啊,估计很多题都忘的差不多了,这次开个题目汇总贴,并附上每道题目的解题连接,方便之后查阅吧~ 如果各位看官们,大神们发现了任何错误,或是代码无法通过OJ,或是有更好的解法,或是有任何疑问,意见和建议的话,请一定要在对应的帖子下面评论区留言告知博.
4164 0
[LeetCode] Substring with Concatenation of All Words
I think the following code is self-explanatory enough. We use an unordered_map counts to record the expected times of each word and another unordered_map seento record the times we have seen.
830 0
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题