不是专门刷LintCode也没时间没耐心，只是刷贴吧看到这个问题就看了一下发现Python真的太棒了。
Substring Anagrams.png
网上有符合要求的代码，反正也只是简单难度。
我自己随便思考出来的方法似乎会超时，见求教各位，这题怎么搞？一贴。
总之就是由于无序而转为统计每个字符出现的个数并比较。
这个思路的C++11版代码，没测试是否超时
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
void func(string word, map<char, size_t>& count)
{
for (size_t i = 0; i <= word.size(); ++i)
{
auto ret = count.insert({ word[i],1 });
if (!ret.second)
++ret.first->second;
}
}
int main() {
//string s = "cbaebabacd";
//string p = "abc";
string s = "abab";
string p = "ab";
vector<int> vec;
map<char, size_t> word_count2;
func(p, word_count2);
for (size_t i = 0; i<s.size() - p.size() + 1; ++i)
{
map<char, size_t> word_count1;
func(s.substr(i, p.size()), word_count1);
if (word_count1 == word_count2)
cout << i;
vec.push_back(i);
}
return 0;
}
这个思路的Python版代码，虽然测试确定会超时，毕竟Python性能差，胜在简洁
from collections import Counter
def func(s, p):
return [i for i in range(len(s)-len(p)+1) if Counter(s[i:i+len(p)]) == Counter(p)]
s, p = "cbaebabacd", 'abc'
print(func(s, p))
问题出在哪呢，真的只是算法本身选的不好吗？
灯光说是字符串切片成本太高，改成前后连接比较好。代码就不再写了。贴吧也有已经AC的代码。
