LeetCode开心刷题十七天——30Substring with Concatenation of All Words

怼烎@ 2023-08-17 15:14 110阅读 0赞

写下小小的心愿，希望在搬家之前，能刷到40

30. Substring with Concatenation of All Words

Hard

554931FavoriteShare

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.

Example 1:

Input:
      s = "barfoothefoobarman",
      words = ["foo","bar"]
    Output: [0,9]
    Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
    The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
      s = "wordgoodgoodgoodbestword",
      words = ["word","good","best","word"]
    Output: []
    
    
    特殊收获：
    1.substr函数
    返回一个新建的初始化为string对象的子串的拷贝string对象。
    子串是，在字符位置pos开始，跨越len个字符（或直到字符串的结尾，以先到者为准）对象的部分。
    2.unordered_map哈希表 count函数

Count函数  
size\_type count ( const key\_type& key ) const  
count函数用以统计key值在unordered\_map中出现的次数。实际上，c++ unordered\_map不允许有重复的key。因此，如果key存在，则count返回1，如果不存在，则count返回0.

3.引入一个新结构类型时，应该想需要什么头文件外部依赖，比如hash表，this structure need extra support \#include<unordered\_map>

4.How do you actually understand a function

eg:

if(!struc.count(t)) break;

In this function,first I thought need add sth after struc(an unordered\_map),but actually this function is to judge whether t in the hashmap,use count function so t need to be as a variable pass into function count.Know where should place function is the first step

5.reset(清零) is an important habit.Especially in counting,many problem comes because of not reset.

6.Assignment is the most effective weapon for supporting ideas

7.Think special case by yourself rather than rely on System judgement

In this code i++ first I use i+=n\*len,i+=len,but it has a special case is such as "aaaaaaa" '"aa"this kinds of duplicate characterised

so at last we can only use i++

#include <iostream>
    #include<vector>
    #include<iostream>
    #include<string>
    #include<stdio.h>
    #include<string.h>
    #include<iomanip>
    #include<vector>
    #include<list>
    #include<queue>
    #include<algorithm>
    #include<stack>
    #include<map>
    #include<unordered_map>
    using namespace std;
    class Solution
    {
    public:
        vector<int> change(string s,vector<string>& word)
        {
            vector<int> res;
            int j=0;
            if(s.size()==0||word.size()==0)
                return res;
            int n=word.size(),len=word[0].size();
            unordered_map<string,int> struc;
            //build a hashMap to store structure
            for(auto wor:word)
            {
                ++struc[wor];
            }
            //prove insert correct
            for(auto wor:word)
            {
                cout<<"struc: "<<wor<<" value:  "<<struc[wor]<<endl;
                //++struc[wor];
            }
            for(int i=0;i<=(int)s.size()-n*len;)
            {
                string sent=s.substr(i,n*len);
                cout<<"sent : "<<sent<<endl;
                unordered_map<string,int> test;
                for(j=0;j<n*len;j+=len)
                {
                    string t=sent.substr(j,len);
                    cout<<"t : "<<t<<endl;
                    //if exist count==1,add !==0 break if not exist break;
                    if(!struc.count(t)) break;
                    ++test[t];
                    if(test[t]>struc[t]) break;
                }
                if(j==n*len) res.push_back(i);
    
            }
            return res;
        }
    };
    int main()
    {
        string s1;
        cin>>s1;
        vector<string> word;
        word.push_back("bar");
        word.push_back("foo");
        word.push_back("the");
        //word.push_back("word");
        //word.push_back("ssd");
    
        vector<int> res;
        Solution s;
        res=s.change(s1,word);
        for(auto re:res)
            cout<<re<<endl;
        return 0;
    }

This method used to first cut sent from s,then cut t from sent.Add extra space.Lower the speed ,if we let j=0;j<n;j++,in this way,we only need cut and space once.Largely save and space faster a little.

The only thing I want to consist in coding is repetition,First clear your mind,In a word,close the book and don't open it until you finish,compare the performance difference between you and it.Finally,make progress!

Improve the code as following:

class Solution
    {
    public:
        vector<int> findSubstring(string s,vector<string>& word)
        {
            vector<int> res;
            int j=0;
            if(s.empty()||word.empty())
                return {};
            int n=word.size(),len=word[0].size();
            unordered_map<string,int> struc;
            //build a hashMap to store structure
            for(auto &wor:word)
            {
                ++struc[wor];
            }
            for(int i=0;i<=(int)s.size()-n*len;++i)
            {
                //string sent=s.substr(i,n*len);
                unordered_map<string,int> test;
                for(j=0;j<n;++j)
                {
                    string t=s.substr(i+j*len,len);
                    if(!struc.count(t)) break;
                    ++test[t];
                    if(test[t]>struc[t]) break;
                }
                if(j==n) res.push_back(i);
    
            }
            return res;
        }
    };

转载于:https://www.cnblogs.com/Marigolci/p/11168945.html