首页 > 代码库 > Substring with Concatenation of All Words

Substring with Concatenation of All Words

  leetcode中有好些题目是这一类型,即找出满足一定条件的字符串子串。有些只要返回一个结果,有些则要返回所有结果。这类题目大体有两个思路,一个是dfs,另一个则是直接遍历,记录遍历过程中的一些状态。此题采用后者,理解起来简单。

  题目并没有说L中的字符串是否可以重复,因此认为是可能重复的。所以算法开始需要对L中的字符串进行一些初步计算,简单来说就是用HashMap进行数量的统计。这是一个很常用的技巧。

  假设L的大小为N,L中字符串长度为len。任意位置都有可能符合最后的结果。因此算法的思路如下:遍历任意位置i,作为起始点。从该位置开始,考察S中N个长度为len的子字符串,用另一个HashMap来记录这N个子字符串的统计结果。如果某个子字符串不是初始统计的HashMap的key,说明不在L中,不符合条件,可以调到下一个位置。如果某个子字符串的统计结果比words中的大,说明该子字符串出现的次数太多了,必然也不符合条件,可以跳到下一个位置。

  当然,i不用遍历到最后一个位置,因为一旦从某个i开始的字符串长度比N*len短,那必然不符合条件。

  c++代码如下:

  

class Solution {public:    vector< int> findSubstring(string S, vector< string> &L) {        vector< int> res;        map< string,int> words;        map< string,int> counts;        int N=L.size();        if(N==0)            return res;        int wordLen=L[0].length();        int NL=wordLen*N;        for(int i=0;i< L.size();i++)        {            words[L[i]]++;        }        for(int i=0;i+NL< =S.length();i++)        {            counts.clear();            int j=0;            for(j=0;j< N;j++)            {                string s=S.substr(i+j*wordLen,wordLen);                if(words.find(s)==words.end())                    break;                ++counts[s];                if(counts[s]>words[s])                    break;            }            if(j==N)            {                res.push_back(i);            }        }        return res;    }};

   上述c++代码中第17行"i+NL< =S.length()",不可以写成"i<=S.length()-NL"。从数学上以及语法上来说,后者没有问题。但是这就涉及一些类型转换等问题。比如S="a",L=["a","a"],则S.leng()-NL=1-2=-1;但是S.length()是size_type类型,我们可以理解为unsigned int型。包含unsigned 和 signed int的表达式,signed int被隐式转换为unsigned int,因此-1的二进制对应unsigned int实际上是一个很大的数,我们就得不到正确的结果了。由此可见,有时候一些日常没注意到的基础常常会给我们造成非常大的困扰。