[LintCode] Substring Anagrams

不是专门刷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的代码。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 174,167评论 25 709
  • 前言 别让忙碌占据了你的锻炼时间,别让应酬成为你身体变差的原因,人活于天地应任意驰骋,身体垮了,谈何人生。 我的现...
    遥想江南阅读 1,151评论 0 50
  • 稍微有点累,躺在被我外甥尿湿又阴干的床上,正在考虑是只洗床单还是床单和褥罩一起洗。对童子尿木有研究啊,气味还是有的...
    Realeyes阅读 569评论 0 0