注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
C++写了两个方法(都不是最优的),复杂度应该是一样的,但是不知道为什么第二个老是超时,有人能帮我看看吗
第一个是两个string 一起loop,
第二个是P先在外面做一个map, 传map进来。
按道理两个都是线性复杂度,但是第二个老是超时- <div> bool match(string&s, int idx, string& p) {</div><div> vector<int> vec(26, 0);</div><div> for (int i = 0; i < p.length(); i++) {</div><div> vec[s[i + idx] - 'a']--;</div><div> vec[p[i] - 'a']++;</div><div> }</div><div>
- </div><div> for (auto item : vec) {</div><div> if (item != 0) return false;</div><div> }</div><div>
- </div><div> return true;</div><div> }</div><div>
- </div><div> bool match(string&s, int idx, unordered_map<char, int> vmap, int plen) {</div><div> for (int i = idx; i < idx + plen; i++) {</div><div> vmap[s[i]]--;</div><div> if (vmap[s[i]] < 0) return false;</div><div> }</div><div>
- </div><div> return true;</div><div> }</div>
复制代码 |