首页 > 代码库 > 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实际上是一个很大的数，我们就得不到正确的结果了。由此可见，有时候一些日常没注意到的基础常常会给我们造成非常大的困扰。