2014
11-18

# LeetCode-Substring with Concatenation of All Words[模拟]

### 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).

// LeetCode, Substring with Concatenation of All Words
// 时间复杂度O(n*m)，空间复杂度O(m)
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& dict) {
size_t wordLength = dict.front().length();
size_t catLength = wordLength * dict.size();
vector<int> result;

if (s.length() < catLength) return result;

unordered_map<string, int> wordCount;

for (auto const& word : dict) ++wordCount[word];

for (auto i = begin(s); i <= prev(end(s), catLength); ++i) {
unordered_map<string, int> unused(wordCount);

for (auto j = i; j != next(i, catLength); j += wordLength) {
auto pos = unused.find(string(j, next(j, wordLength)));

if (pos == unused.end() || pos->second == 0) break;

if (--pos->second == 0) unused.erase(pos);
}

if (unused.size() == 0) result.push_back(distance(begin(s), i));
}

return result;
}
};

1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

2. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}

3. [email protected]

4. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)