串联所有单词的子串

题目

给定一个字符串 s 和一个字符串数组 words. words 中所有字符串长度相同.

s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串.

例如, 如果 words = ["ab", "cd", "ef"], 那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", "efcdab" 都是串联子串. "acdbef" 不是串联子串, 因为他不是任何 words 排列的连接. 返回所有串联字串在 s 中的开始索引. 你可以以任意顺序返回答案.

提示:

• 1 <= s.length <= 10⁴
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

示例

输入: s = "barfoothefoobarman", words = ["foo", "bar"]
输出: [0, 9]
解释: 因为 words.length == 2 同时 words[i].length == 3, 连接的子字符串的长度必须为 6.
子串 "barfoo" 开始位置是 0. 它是 words 中以 ["bar", "foo"] 顺序排列的连接.
子串 "foobar" 开始位置是 9. 它是 words 中以 ["foo", "bar"] 顺序排列的连接.
输出顺序无关紧要. 返回 [9,0] 也是可以的.

输入: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"]
输出: []
解释: 因为 words.length == 4 并且 words[i].length == 4, 所以串联子串的长度必须为 16.
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接.
所以我们返回一个空数组.

输入: s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]
输出: [6, 9, 12]
解释: 因为 words.length == 3 并且 words[i].length == 3, 所以串联子串的长度必须为 9.
子串 "foobarthe" 开始位置是 6. 它是 words 中以 ["foo", "bar", "the"] 顺序排列的连接.
子串 "barthefoo" 开始位置是 9. 它是 words 中以 ["bar", "the", "foo"] 顺序排列的连接.
子串 "thefoobar" 开始位置是 12. 它是 words 中以 ["the", "foo", "bar"] 顺序排列的连接.

题解

JavaScript

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
  const wordMap = new Map()
  for (const word of words) {
    wordMap.set(word, wordMap.has(word) ? wordMap.get(word) + 1 : 1)
  }
  const wordLen = words[0].length
  const subStrLen = wordLen * words.length
  const result = []

  for (let i = 0; i + subStrLen <= s.length; i++) {
    let count = 0
    const map = new Map()
    const subStr = s.slice(i, i + subStrLen)

    for (let j = 0; j < subStrLen; j += wordLen) {
      const word = subStr.slice(j, j + wordLen)
      if (!wordMap.has(word)) break
      map.set(word, map.has(word) ? map.get(word) + 1 : 1)
      if (map.get(word) === wordMap.get(word)) count++
    }

    if (count === wordMap.size) {
      result.push(i)
    }
  }

  return result
}

Rust

use std::collections::HashMap;
use std::str;

pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
    let s = s.as_bytes();
    let m = s.len();
    let n = words.len();
    let w = words[0].len();

    let mut map = HashMap::new();
    for word in words {
        map.entry(word).and_modify(|e| *e += 1).or_insert(1);
    }

    let mut res = vec![];
    for i in 0..m {
        let end = i + n * w;
        if end > m {
            break;
        }

        let sub_string = str::from_utf8(&s[i..end]).unwrap();
        let mut sub_map = HashMap::new();

        for j in (0..(n * w)).step_by(w) {
            let sub = sub_string[j..(j + w)].to_string();
            if !map.contains_key(&sub) {
                break;
            }
            sub_map.entry(sub).and_modify(|e| *e += 1).or_insert(1);
        }

        if map == sub_map {
            res.push(i as i32);
        }
    }

    res
}