Leetcode 30: Substring with Concatenation of All Words

Put words into hash map, step through each char in s checking for words in the hashmap. If we find a word then step through to the character after that match and attempt to match remaining words with the hash map. We need two separate hash maps, one will hold the counts of the words (as they can appear more than once in the words array) and the other will hold the counts for the current matching sequence. I call then counts and countsMatch respectively. It doesn’t make much difference how we reset countsMatch, I initially looped through resetting each element but then used countsMatch.clear(). One optimisation that makes a big difference is if we stop our outer loop of s when it is impossible to make a match, i.e. words.size() * words[0].size() characters before the end of s.

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *