30. Substring with Concatenation of All Words

Tags
  1. Hash Table
  2. Two Pointers
  3. String

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

题意：

将会给你提供一个字符串s，以及一个数组words,words数组中的字符串长度都是一样的。在字符串s中找到所有含有words数组中每个子项字符只组合一次且无任何其它介入字符的子字符串的起始位置。

分析：

看到这个题目的时候感觉和28题很像，所以最开始的想法是按照28题的基本思路来做，但是发现如果是把words数组中的字符串来拼接比较的话，感觉就非常麻烦了。但是题目中有一点很重要就是说words数组中的字符串长度都是一样，且每个只组合一次，那么如果反过来，循环将s字符串截取出来的子字符串与words数组中每一个进行一一比较，那么思路就比较清晰了。但是如果按照28的做法来算的话，时间复杂度肯定就是三次方了。所以想到了通过对象或者Map来比较就能将复杂度降到2次方了。于是就按照这个思路进行了下去，后面查看discss中一些别人的做法也基本上吻合。

思路：

通过分析得到了大概的思路，后续通过题目理解以及多次试验，具体的思路如下：

  1. 循环words数组，得到每个子项字符串组合后大字符串出现的次数，通过对象或者Map(counts)来存。（不同字符串只会出现1次，若有相同的才会出现多次）
  2. 按照28题的做法，从头开始到s最多能比对到的位置循环截取与words数组子项相同长度的字符串，然后与之前存的(counts)进行比对，记录出现的次数。
  3. 如果相加，则相加的次数不大于counts中的记录的次数，就说明符合条件。
  4. 如果相减，则相减之后，最终size为0，则说明符合条件
复杂度：

时间复杂度O(n2)

Js实现：

  1. 加法

    /**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function(s, words) {
 const counts = {};
 const n = s.length, num = words.length, len = words[0].length;
 const indexArr = [];
 words.forEach((word, i) => {
     if(counts[word]) {
         counts[word]++;
     } else {
         counts[word] = 1;
     }
 });

 for(let i = 0; i < n - num * len + 1; i++) {
     const seen = {};
     for(let j = 0; j < num; j++) {
         const word = s.substr(i + j*len, len);
         if(counts[word]) {
             if(seen[word]){
                 seen[word]++;
             }else {
                 seen[word] = 1;
             }

             if(seen[word] > counts[word]) {
                 break;
             } else if(j === num - 1) {
              indexArr.push(i);
             } 
         } else {
             break;
         }
     }
 }
 return indexArr; 
};

  2. 减法

    /**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function(s, words) {
const map = new Map();
const n = s.length, num = words.length, len = words[0].length;
const indexArr = [];
words.forEach((word, i) => {
    const count = map.get(word);
    if(count) {
        map.set(word,count+1);
    } else {
        map.set(word, 1);
    }
});

for(let i = 0; i < n - num * len + 1; i++) {
    const copy = new Map([...map]);
    for(let j = 0; j < num; j++) {
        const word = s.substr(i + j*len, len);
        const count = copy.get(word);
        if(count) {
            if(count === 1) {
                copy.delete(word);
            } else {
               copy.set(word, count - 1);
            }
            if(copy.size === 0) {
                indexArr.push(i);
                break;
            }
        } else {
            break;
        }
    }
}
return indexArr; 
};

results matching ""

    No results matching ""