与所有单词相关联的字串

[louzhedong]

习题

出处：LeetCode 算法第30题

给定一个字符串 s 和一些长度相同的单词 **words。**在 s 中找出可以恰好串联 words 中所有单词的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1:

输入:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出: [0,9]
解释: 从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:

输入:
  s = "wordgoodstudentgoodword",
  words = ["word","student"]
输出: []

思路

方法一，将words拼成字符串，去s里面寻找是否匹配，但是时间复杂度太高，数据多的时候会超时

方法二，由于单词的长度是固定的，所以可以在s中截取单词长度的字符串，去匹配words中的单词

解答

方法一

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */

function copy(array) {
  var result = [];
  for (var i = 0, len = array.length; i < len; i++) {
    result.push(array[i]);
  }
  return result;
}

var findSubstring = function (s, words) {
  var result = [];
  if (s.length == 0 || words.length == 0) {
    return result;
  }
  var length = words.length;
  var wordString = words.join('');
  var wordLength = wordString.length;
  if (s.length === wordLength && (s.indexOf(wordString) >= 0)) {
    result.push(s.indexOf(wordString));
  } else {
    var oneWordLength = words[0].length;
    var temp = [];
    for (var i = 0; i < length; i++) {
      temp.push(words[i]);
      var copyWords = copy(words);
      copyWords[i] = '';
      DFS(s, length, temp, result, copyWords, oneWordLength);
      temp.pop();
    }
  }
  return Array.from(new Set(result));
};

function DFS(s, length, temp, result, copyWords, oneWordLength) {
  if (temp.length == length) {
    var tempValue = temp.join('');
    for (var i = 0; i <= s.length - oneWordLength; i += oneWordLength) {
      var index = s.indexOf(tempValue, i);
      if (index >= 0) {
        result.push(index);
      }
    }
  }
  var empty = true;
  for (var j = 0; j < copyWords.length; j++) {
    if (copyWords[j] != '') {
      empty = false;
    }
  }
  while (!empty) {
    for (var i = 0; i < copyWords.length; i++) {
      if (copyWords[i] != '') {
        var tempValue = copyWords[i];
        temp.push(copyWords[i]);
        copyWords[i] = '';
        DFS(s, length, temp, result, copyWords, oneWordLength);
        for (var j = 0; j < copyWords.length; j++) {
          if (copyWords[j] != '') {
            empty = false;
          } else {
            empty = true;
          }
        }
        temp.pop();
        copyWords[i] = tempValue;
      }
    }
  }
}

方法二

var findSubstring2 = function(s, words) {
  var result = [];
  if(words.length===0)return result;
  let len = words[0].length;
  
  function find(str){
      let s,begin = 0;
      while(str.length >= len){
          s = str.substr(0,len);
          let index = words.indexOf(s,begin);
          if(index >= 0){
              let tmp = words[begin];
              words[begin] = words[index];
              words[index] = tmp;
              begin++;
              str=str.substr(len);
              if(begin==words.length) return true;
          }else{
              return false;
          }
      }
  }
  for (let i=0;i<=s.length-len;i++){
      if(find(s.substr(i)))  result.push(i);
  }
  return result;
};