CS 102 pt 0: Finding Substring Concatenations

This is not real course work, and I'm not taking any CS 102 class. I thought it might be worthwhile to post notes on basic CS concepts once in a while. I do LeetCode problems sometimes to stay sharp in different programming languages. I did this problem today and decided to write an explainer.

Problem Statement

Given a string and a list of equal length words, find all substrings that are a combination of all words.

Algorithm

A naive approach might check a lot of potential combinations. A more standard approach would use comparison between maps.

Naive Approach

One starting index at a time, scan to the right while comparing candidate words from the list. If a word is found, eliminate it and keep scanning. If all words are found, we found an overall match at the starting index, otherwise we found nothing.

Standard Approach

First, count how many times each word appears in the word list and put it in a map. Then split the string into fixed-length chunks and slide a window with the same number of words as the list. For each window, compare word counts to the target map.