leetcode: Substring with Concatenation of All Words

Problem Description:

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).

Solution and Precautions:

Brute force approach works here. Test every possible substring in S with the length of the concatenation of all words against the word set to see if this substring consists of every word in the given set. To do the test, one can use hash table to check if the word in the substring is in the given set or not. Because every word are of the same size, then once the substring is fixed, the words splitting in this substring is determined,

Written on May 20, 2013