[LeetCode] 30. Substring with Concatenation of All Words

轉自 LeetCode

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.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

<Solution>

這題的題意是，在 words 裡面的字串組成的 string (順序不一定)，是 s 裡面的一個 sub-string

例如 foobar、barfoo 是不是有在 s 裡面

有的話，把 substring 的開頭字元的 index 回傳

解題想法如下(參考資料)

• 先用一個 hash map 把 words 裡面的字存起來，key 是 string，value 是此 string 在 words 裡面出現的次數

• 因為題目有說在 words 裡面的 string 長度都是一樣的，所以可以根據其長度來抓取 substring

• 每個 substring 都先去步驟一的 hash map 裡面查是否存在，不存在就直接 break，代表此 substring 是不在 words 裡的

• 如果存在，那再用一個 hash map 存起來，key 就是 substring，value 是此 substring 出現的次數。因為題目有說，每個 words 裡面的 string 只能用一次，所以如果 substring 出現次數比 words 裡的還多，那也是不符合

code 如下

c++

kotlin