LeetCode OJ:Substring with Concatenation of All Words_given a list of words l, that are all the same len

作者：我家自动化 | 2024-03-16 23:17:19

踩

given a list of words l, that are all the same length,andg a string, s, find

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

算法思想：

暴力


class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        
        map<string, int> words;    
        map<string, int> count;    
        vector<int> result;    
        int wordNum = L.size();    
        if (wordNum == 0) return result;    
        for (int i = 0; i < wordNum; ++i)    
            ++words[L[i]];    
            
        int wordSize = L[0].size();    
        int slength = S.size();    
        for (int i = 0; i <= slength - wordSize*wordNum; ++i)    
        {    
            count.clear();    
            int j = 0;    
            for (; j < wordNum; ++j)    
            {    
                string str = S.substr(i+j*wordSize, wordSize);     
                if(words.find(str) == words.end())      
                    break;      
                ++count[str];      
                if(count[str] > words[str])      
                    break;      
            }    
            if (j == wordNum) result.push_back(i);    
        }    
        return result;  
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/252626