Substring with Concatenation of All WordsFeb 24 '125071 / 18608
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).
注:未通过所有case
“aaa”, [a, b],这个case我自己返回是空,但是在leetcode上返回(0,1)。让我很郁闷。
假如unordered_map可以算作是O(1)的话,则这个算法应该是O(n),n = S.size();
class Solution { public: unordered_map<string, int> dic; vector<int> t; void load(const string& s, const vector<string> &l) { int n = l.size(); int cnt = 0; for (int i = 0; i < n; ++i) { auto it = dic.find(l[i]); if (it == dic.end()) { dic[l[i]] = cnt++; t.push_back(1); } else { t[it->second]++; } } } vector<int> findSubstring(string S, vector<string> &L) { vector<int> res; int n = L.size(); int len = S.size(); int K = L[0].size(); load(S, L); vector<int> v(len); for (int i = 0; i < len - K; ++i) { auto it = dic.find(S.substr(i, K)); if (it == dic.end()) v[i] = -1; else v[i] = it->second; } int total = 0, last = len - K * n; vector<bool> mk(len, false); res.clear(); for (int i = 0; i <= last; ++i) { if (mk[i]) continue; int start = i, end, cur; while (start <= last && dic.find(S.substr(start, K)) == dic.end()) mk[start] = true,start += K; if (start > last) continue; if (n == 1) { res.push_back(start); mk[start] = true; continue; } end = start + K; vector<int> cnt(t); total = 1; auto it = dic.find(S.substr(start, K)); cnt[it->second]--; while (end < len) { auto ie = dic.find(S.substr(end, K)); if (ie == dic.end()) { while (start <= end) mk[start] = true, start += K; break; } else { cur = ie->second; if (cnt[cur] == 0) { while (start <= end) { mk[start] = true; cnt[v[start]]++; total--; if (cur == v[start]) break; start += K; } } cnt[cur]--; total ++; if (total == n) { res.push_back(start); cnt[v[start]]++; total--; mk[start]=true; start += K; } end += K; } } } return res; } };
相关推荐
leetcode 跳跃 LeetCode Exercises from leetcode. All the exercises is uesd by microsoft to interview. The following is the number of the questions form Leetcode. 4 寻找两个正序数组的中位数 median of ...
Concatenation of All Words 哈希表 注意匹配方向 Valid Sudoku 数组 遍历 Sudoku Solver 深度优先遍历 回溯 先检查后修改 Group Anagrams 排序 unordered_map Minimum Window Substring 两个指针遍历 map Maximal ...
LeetCode of algorithms with golang solution(updating).
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
Here is the classification of all `468` questions. For more questions and solutions, you can see my [LintCode](https://github.com/kamyu104/LintCode) repository. I'll keep updating for full summary and...
算法相关知识储备 LeetCode with Python
算法 Leetcode刷题手册 labuladong的算法小抄官方完整版
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
leetcode-with-python3 ARRAY 1.两数之和 4.寻找两个有序数组的中位数 11.盛最多水的容器 26.删除排序数组中的重复项 15.三数之和 16.最接近的三数之和 27.移除元素 35.搜索插入位置 66.加一 88.合并两个有序数组
java;LeetCode前一百道;有题目;多重解法
with leetcode Practice List String 28 14 58 387 383 344 151 186 345 205 293 294 290 242 49 249 87 161 38 358 316 271 168 171 13 12 273 246 247 提高 157 158 68 65 Substring 76 30 3 340 395 159 ...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
LeetCode 刷题笔记 with Java 51-100(暗黑版).pdf
With Most Water LeetCode 19 Remove Nth Node From End of List LeetCode 42 Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - ...
leetcode_with_typescript
Leetcode-with-python python solution for leetcode 数组 [283] 移动零 双指针 [345] 反转字符串中的元音字母 图 [785] 判断二分图 [207] 课程表 [886] 可能的二分法 [133] 克隆图 [684] 冗余连接 动态规划 [62] ...
周赛难度每周-Leetcode-with-MS 业主:兰 时间:从 19.12.11 Week6 动态规划 指数 标题 解决方案 验收 困难 70 √ 45.6% 简单的 198 √ 41.5% 简单的 303 √ 40.8% 简单的 64 √ 49.7% 中等的 309 √ 45.2% 中等的 ...
Reverse words in a string-leetcode
leetcode-with-js Solving LeetCode problems using JavaScript。 题目涵盖了 LeetCode、「程序员的面试金典」(Cracking the Coding Interview)[第六版] 以及「剑指 offer」。 I. 项目说明 项目结构 1. src src ...
Solution to LeetCode written by C++. All codes are tested to ACCEPTED on LeetCode online judge. Basic data structure and algorithm sample codes.