This is a Leetcode problem:
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
A couple of sample inputs/outputs:
s = "barfoobarthefoobarman"
words = ["bar","foo","the"]
output = [3,6,9]
s = "lingmindraboofooowingdingbarrwingmonkeypoundcake"
words = ["fooo","barr","wing","ding","wing"]
output = [13]
My code
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> answer;
int slen = s.length(), wlen = words[0].length(), wnum = words.size();
auto start = words.begin(), end = words.end(), bound = start, found = end;
// traverse every possible offset with respect to wlen
for (int i = 0; i < wlen; ++i) {
// [bound] delineates the separation between two sections of the word list
// left of [bound] are the words that have been found so far - I'll call this section words(found)
// [bound] to [end] are words still to be found - I'll call this words(left)
// I'll use words(found) as a virtual queue, pushing words on as they're found, popping expired found words
bound = start;
// traverse consecutive word-length substrings from offset i
// terminate when the number of positions left to check < number of words left to find
for (int j = i; j <= slen-wlen*(end-bound); j += wlen) {
// look for substring first in words(left)
auto found = std::find(bound, end, s.substr(j, wlen));
if (found != end) {
std::iter_swap(found, bound++); // 'push' [found] onto words(found)
} else {
// if substring not found in words(left), look in words(found)
found = std::find(start, bound, s.substr(j, wlen));
if (found != bound) {
// if the substring is one of the words(found),
// we need to 'pop' all words up to and including [found] from words(found)
// (which we can do using a rotation) and push [found] back onto the end
std::iter_swap(found, bound); // pushing first is simpler
bound = std::rotate(start, found+1, bound+1); // pop
} else {
// if current substring is not in the word list at all, reset words(found) to nil
bound = start;
}
}
if (bound == end) {
// if words(found) == [words], we've found an answer! push it on
answer.push_back(j-wlen*(wnum-1));
std::rotate(start, start+1, bound--); // pop first word off words(found)
}
}
}
return answer;
}
};
Explanation
In my solution, the intuition is that as I loop through consecutive word positions (ie. incrementing by word length), building up a concatenation of words, I need to keep track of words I've found so far in a queue. If the substring I'm looking at is one of the words I'm yet to find, I push it onto the queue. Otherwise, if it's a word that's already in my concatenation-so-far, I need to pop everything off the queue up to and including that word, then push it back onto the end. (Think about the sample input above when I encounter "foobarfoo"
.) If it's not a word at all, clear the queue.
Rather than creating a queue, though, I construct a 'virtual' one in-place, using an iterator to mark the division in the list words
between words-found and words-still-to-find. This way, when I 'pop' words by rotating words
and repositioning the iterator, those words automatically end up in the words-still-to-find side of the list.
Discussion
I haven't seen a solution like this posted on the site. Most of them use one or two unordered_maps, but from what I can see they either don't iterate through word-positions like I am, or they don't address the queue-like nature of doing so. Using some kind of hashmap definitely improves efficiency, but my solution remains competitive (beating 70% of C++ submissions, at 48ms) because of its lack of overheads and efficient iteration (I think). As a bonus, it has constant space complexity.
Questions:
- Am I right in thinking the time complexity is \$O(n)\$?
- Does this approximate a known algorithm?
- Is there a more appropriate data structure I could be using here? I want to introduce a hashmap whose values somehow point to a queue, but I can't figure out how to make all the pieces fit.
add_standard_review(review::missing_headers); add_standard_review(review::using_namespace);
- also, why is this an instance method of a class? It looks like it could be a plain function. \$\endgroup\$ – Toby Speight Jan 26 '18 at 14:31std
namespace and I guess automatically includes required headers. It also requires answers to be formatted in terms of aSolution
class. I was going to add amain()
that used the item on test data, but I saw other Leetcode-based questions on here that didn't, and figured it must be understood. I should've mentioned it in the question though. \$\endgroup\$ – Igid Jan 26 '18 at 15:22