力扣00030.串联所有单词的子串

发表于 分类于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 12 分钟
串联所有单词的子串、哈希表、字符串、滑动窗口、困难

题目描述

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

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

  • 例如，如果 words = [“ab”,”cd”,”ef”]， 那么 “abcdef”， “abefcd”，”cdabef”， “cdefab”，”efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：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] 也是可以的。

示例 2：

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

示例 3：

输入：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”] 顺序排列的连接。

提示：

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

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if (s.empty() || words.empty()) {
            return result;
        }
        int wordLen = words[0].length();
        int totalLen = words.size() * wordLen;
        unordered_map<string, int> wordCount;
        for (const string& word : words) {
            wordCount[word]++;
        }
        for (int i = 0; i < wordLen; ++i) {
            int left = i, right = i;
            unordered_map<string, int> currentCount;
            while (right + wordLen <= s.length()) {
                string currentWord = s.substr(right, wordLen);
                right += wordLen;
                currentCount[currentWord]++;
                while (currentCount[currentWord] > wordCount[currentWord]) {
                    string leftWord = s.substr(left, wordLen);
                    left += wordLen;
                    currentCount[leftWord]--;
                }
                if (right - left == totalLen) {
                    result.push_back(left);
                }
            }
        }
        return result;
    }
};

结果

执行用时 : 105 ms, 击败 21.11% 使用 C++ 的用户

内存消耗 : 48.18 MB, 击败 9.14% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.isEmpty() || words == null || words.length == 0) {
            return result;
        }
        int wordLen = words[0].length();
        int totalLen = words.length * wordLen;
        Map<String, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < wordLen; i++) {
            int left = i, right = i;
            Map<String, Integer> currentCount = new HashMap<>();
            while (right + wordLen <= s.length()) {
                String currentWord = s.substring(right, right + wordLen);
                right += wordLen;
                currentCount.put(currentWord, currentCount.getOrDefault(currentWord, 0) + 1);
                while (currentCount.get(currentWord) > wordCount.getOrDefault(currentWord, 0)) {
                    String leftWord = s.substring(left, left + wordLen);
                    left += wordLen;
                    currentCount.put(leftWord, currentCount.get(leftWord) - 1);
                }
                if (right - left == totalLen) {
                    result.add(left);
                }
            }
        }
        return result;
    }
}

结果

执行用时 : 22 ms, 击败 54.43% 使用 Java 的用户

内存消耗 : 44.55 MB, 击败 24.02% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        result = []
        if not s or not words:
            return result
        word_len = len(words[0])
        total_len = len(words) * word_len
        word_count = Counter(words)
        for i in range(word_len):
            left, right = i, i
            current_count = Counter()
            while right + word_len <= len(s):
                current_word = s[right:right + word_len]
                right += word_len
                current_count[current_word] += 1
                while current_count[current_word] > word_count[current_word]:
                    left_word = s[left:left + word_len]
                    left += word_len
                    current_count[left_word] -= 1
                if right - left == total_len:
                    result.append(left)
        return result

结果

执行用时 : 117 ms, 击败 65.90% 使用 Python 的用户

内存消耗 : 11.96 MB, 击败 97.05% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        result = []
        if not s or not words:
            return result
        word_len = len(words[0])
        total_len = len(words) * word_len
        word_count = Counter(words)
        for i in range(word_len):
            left, right = i, i
            current_count = Counter()
            while right + word_len <= len(s):
                current_word = s[right:right + word_len]
                right += word_len
                current_count[current_word] += 1
                while current_count[current_word] > word_count[current_word]:
                    left_word = s[left:left + word_len]
                    left += word_len
                    current_count[left_word] -= 1
                if right - left == total_len:
                    result.append(left)
        return result

结果

执行用时 : 104 ms, 击败 76.85% 使用 Python3 的用户

内存消耗 : 17.09 MB, 击败 38.99% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct {
    char key[32];
    int val;
    UT_hash_handle hh;
} HashItem;

int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){    
    int m = wordsSize, n = strlen(words[0]), ls = strlen(s);
    int *res = (int *)malloc(sizeof(int) * ls);
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (i + m * n > ls) {
            break;
        }
        HashItem *diff = NULL;
        char word[32] = {0};
        for (int j = 0; j < m; j++) {
            snprintf(word, n + 1, "%s", s + i + j * n);
            HashItem * pEntry = NULL;
            HASH_FIND_STR(diff, word, pEntry);
            if (NULL == pEntry) {
                pEntry = (HashItem *)malloc(sizeof(HashItem));
                strcpy(pEntry->key, word);
                pEntry->val = 0;
                HASH_ADD_STR(diff, key, pEntry);
            } 
            pEntry->val++;            
        }
        for (int j = 0; j < m; j++) {
            HashItem * pEntry = NULL;
            HASH_FIND_STR(diff, words[j], pEntry);
            if (NULL == pEntry) {
                pEntry = (HashItem *)malloc(sizeof(HashItem));
                strcpy(pEntry->key, words[j]);
                pEntry->val = 0;
                HASH_ADD_STR(diff, key, pEntry);
            } 
            pEntry->val--;
            if (pEntry->val == 0) {
                HASH_DEL(diff, pEntry);
                free(pEntry);
            }
        }
        for (int start = i; start < ls - m * n + 1; start += n) {
            if (start != i) {
                char word[32];
                snprintf(word, n + 1, "%s", s + start + (m - 1) * n);
                HashItem * pEntry = NULL;
                HASH_FIND_STR(diff, word, pEntry);
                if (NULL == pEntry) {
                    pEntry = (HashItem *)malloc(sizeof(HashItem));
                    strcpy(pEntry->key, word);
                    pEntry->val = 0;
                    HASH_ADD_STR(diff, key, pEntry);
                } 
                pEntry->val++;
                if (pEntry->val == 0) {
                    HASH_DEL(diff, pEntry);
                    free(pEntry);
                }
                snprintf(word, n + 1, "%s", s + start - n);
                pEntry = NULL;
                HASH_FIND_STR(diff, word, pEntry);
                if (NULL == pEntry) {
                    pEntry = (HashItem *)malloc(sizeof(HashItem));
                    strcpy(pEntry->key, word);
                    pEntry->val = 0;
                    HASH_ADD_STR(diff, key, pEntry);
                } 
                pEntry->val--;
                if (pEntry->val == 0) {
                    HASH_DEL(diff, pEntry);
                    free(pEntry);
                }
            }
            if (HASH_COUNT(diff) == 0) {
                res[pos++] = start;
            }
        }
        HashItem *curr, *tmp;
        HASH_ITER(hh, diff, curr, tmp) {
            HASH_DEL(diff, curr);  
            free(curr);      
        }
    }
    *returnSize = pos;
    return res;
}

结果

执行用时 : 998 ms, 击败 50.36% 使用 C 的用户

内存消耗 : 28.31 MB, 击败 41.85% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
        List<int> result = new List<int>();
        if (string.IsNullOrEmpty(s) || words == null || words.Length == 0) {
            return result;
        }
        int wordLen = words[0].Length;
        int totalLen = wordLen * words.Length;
        int wordCount = words.Length;
        Dictionary<string, int> wordCounts = new Dictionary<string, int>();
        foreach (string word in words) {
            if (wordCounts.ContainsKey(word)) {
                wordCounts[word]++;
            } else {
                wordCounts[word] = 1;
            }
        }
        for (int i = 0; i <= s.Length - totalLen; i++) {
            Dictionary<string, int> currentWordCounts = new Dictionary<string, int>(wordCounts);
            int j;
            for (j = 0; j < totalLen; j += wordLen) {
                string currentWord = s.Substring(i + j, wordLen);
                if (currentWordCounts.ContainsKey(currentWord) && currentWordCounts[currentWord] > 0) {
                    currentWordCounts[currentWord]--;
                } else {
                    break;
                }
            }
            if (j == totalLen) {
                result.Add(i);
            }
        }
        return result;
    }
}

结果

执行用时 : 1752 ms, 击败 31.63% 使用 C# 的用户

内存消耗 : 68.71 MB, 击败 15.31% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    let result = [];
    if (!s || !words || words.length === 0) {
        return result;
    }
    let wordLen = words[0].length;
    let totalLen = wordLen * words.length;
    let wordCount = words.length;
    let wordCounts = new Map();
    for (let word of words) {
        if (wordCounts.has(word)) {
            wordCounts.set(word, wordCounts.get(word) + 1);
        } else {
            wordCounts.set(word, 1);
        }
    }
    for (let i = 0; i <= s.length - totalLen; i++) {
        let currentWordCounts = new Map(wordCounts);
        for (let j = 0; j < totalLen; j += wordLen) {
            let currentWord = s.substring(i + j, i + j + wordLen);
            if (currentWordCounts.has(currentWord) && currentWordCounts.get(currentWord) > 0) {
                currentWordCounts.set(currentWord, currentWordCounts.get(currentWord) - 1);
            } else {
                break;
            }
        }
        if (Array.from(currentWordCounts.values()).every(count => count === 0)) {
            result.push(i);
        }
    }
    return result;
};

结果

执行用时 : 907 ms, 击败 54.95% 使用 JavaScript 的用户

内存消耗 : 56.55 MB, 击败 16.64% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function findSubstring(s: string, words: string[]): number[] {
    const result: number[] = [];
    if (!s || !words || words.length === 0) {
        return result;
    }
    const wordLen: number = words[0].length;
    const totalLen: number = wordLen * words.length;
    const wordCount: number = words.length;
    const wordCounts: Map<string, number> = new Map();
    for (const word of words) {
        if (wordCounts.has(word)) {
            wordCounts.set(word, wordCounts.get(word)! + 1);
        } else {
            wordCounts.set(word, 1);
        }
    }
    for (let i = 0; i <= s.length - totalLen; i++) {
        const currentWordCounts: Map<string, number> = new Map(wordCounts);
        for (let j = 0; j < totalLen; j += wordLen) {
            const currentWord: string = s.substring(i + j, i + j + wordLen);
            if (currentWordCounts.has(currentWord) && currentWordCounts.get(currentWord)! > 0) {
                currentWordCounts.set(currentWord, currentWordCounts.get(currentWord)! - 1);
            } else {
                break;
            }
        }
        if (Array.from(currentWordCounts.values()).every(count => count === 0)) {
            result.push(i);
        }
    }
    return result;
}

结果

执行用时 : 874 ms, 击败 73.21% 使用 TypeScript 的用户

内存消耗 : 57.38 MB, 击败 6.25% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {

    /**
     * @param String $s
     * @param String[] $words
     * @return Integer[]
     */
    function findSubstring($s, $words) {
        $result = [];
        if (empty($s) || empty($words)) {
            return $result;
        }
        $wordLen = strlen($words[0]);
        $totalLen = $wordLen * count($words);
        $wordCount = count($words);
        $wordCounts = [];
        foreach ($words as $word) {
            if (isset($wordCounts[$word])) {
                $wordCounts[$word]++;
            } else {
                $wordCounts[$word] = 1;
            }
        }
        for ($i = 0; $i <= strlen($s) - $totalLen; $i++) {
            $currentWordCounts = $wordCounts;
            for ($j = 0; $j < $totalLen; $j += $wordLen) {
                $currentWord = substr($s, $i + $j, $wordLen);
                if (isset($currentWordCounts[$currentWord]) && $currentWordCounts[$currentWord] > 0) {
                    $currentWordCounts[$currentWord]--;
                } else {
                    break;
                }
            }
            if (array_sum($currentWordCounts) === 0) {
                $result[] = $i;
            }
        }
        return $result;
    }
}

结果

执行用时 : 1420 ms, 击败 100.00% 使用 PHP 的用户

内存消耗 : 20.54 MB, 击败 -% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        guard !s.isEmpty, !words.isEmpty, !words[0].isEmpty else {
            return []
        }
        let wordLength = words[0].count
        let wordCount = words.count
        let totalLength = wordLength * wordCount
        let sArray = Array(s)
        var results: [Int] = []
        var wordsDict: [String: Int] = [:]
        for word in words {
            wordsDict[word, default: 0] += 1
        }
        for i in 0..<wordLength {
            var left = i
            var right = i
            var currentDict: [String: Int] = [:]
            var valid = 0
            while right + wordLength <= s.count {
                let currentWord = String(sArray[right..<right + wordLength])
                right += wordLength
                if let count = currentDict[currentWord] {
                    currentDict[currentWord] = count + 1
                    if count + 1 == wordsDict[currentWord] {
                        valid += 1
                    }
                }
                while right - left >= totalLength {
                    if valid == wordsDict.count {
                        results.append(left)
                    }
                    let leftWord = String(sArray[left..<left + wordLength])
                    left += wordLength
                    if let count = currentDict[leftWord] {
                        if count == wordsDict[leftWord] {
                            valid -= 1
                        }
                        currentDict[leftWord] = count - 1
                    }
                }
            }
        }
        return results
    }
}

结果

执行用时 : 272 ms, 击败 25.00% 使用 Swift 的用户

内存消耗 : 16.11 MB, 击败 8.33% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class Solution {
    fun findSubstring(s: String, words: Array<String>): List<Int> {
        val result = mutableListOf<Int>()
        if (s.isEmpty() || words.isEmpty() || s.length < words[0].length || s.length < words[0].length * words.size) {
            return result
        }
        val wn = words[0].length
        val count = words.groupBy { it }.mapValues { it.value.size }
        val wordFreq = IntArray(count.size)
        val uniqWords = count.keys.toList()
        uniqWords.forEachIndexed { index, w -> wordFreq[index] = count[w]!! }
        val matchIndex = IntArray(s.length) { -1 }
        ACTree(uniqWords).match(s) { pos, strIndex, _ -> matchIndex[pos] = strIndex }
        val freq = wordFreq.clone()
        for (i in 0 until wn) {
            var j = i
            while (j < matchIndex.size && matchIndex[j] == -1) j += wn
            var dist = words.size
            var left = j
            var right = j
            wordFreq.copyInto(freq)
            while (right < matchIndex.size) {
                if (matchIndex[right] == -1) {
                    right += wn
                    left = right
                    dist = words.size
                    wordFreq.copyInto(freq)
                    continue
                }
                if (--freq[matchIndex[right]] >= 0) dist--
                right += wn
                while (dist == 0) {
                    if (right - left == words.size * wn) {
                        result.add(left)
                    }
                    if (++freq[matchIndex[left]] > 0) dist++
                    left += wn
                }
            }
        }
        return result
    }
    class ACTree(val strs: List<String>) {
        val root = AcNode('a')
        init {
            strs.forEachIndexed { i, it -> putString(i, it) }
            buildFailurePointer()
        }
        class AcNode(var data: Char) {
            val children = arrayOfNulls<AcNode>(26)
            var isEndingChar = false
            var length = 0
            var fail: AcNode? = null
            var strIndex = 0
        }
        private fun putString(index: Int, str: String) {
            var p = root
            str.forEach {
                val next = p.children[it - 'a']
                if (next != null) {
                    p = next
                } else {
                    val new = AcNode(it)
                    new.length = p.length + 1
                    p.children[it - 'a'] = new
                    p = new
                }
            }
            p.isEndingChar = true
            p.strIndex = index
        }
        private fun buildFailurePointer() {
            val queue: Queue<AcNode> = LinkedList()
            root.fail = null
            queue.add(root)
            while (queue.isNotEmpty()) {
                val p: AcNode = queue.remove()
                for (i in 0..25) {
                    val pc = p.children[i] ?: continue
                    if (p == root) {
                        pc.fail = root
                    } else {
                        var q = p.fail
                        while (q != null) {
                            val qc = q.children[pc.data - 'a']
                            if (qc != null) {
                                pc.fail = qc
                                break
                            }
                            q = q.fail
                        }
                        if (q == null) {
                            pc.fail = root
                        }
                    }
                    queue.add(pc)
                }
            }
        }
        fun match(text: String, action: (pos: Int, strIndex: Int, str: String) -> Unit) {
            val n = text.length
            var p: AcNode? = root
            for (i in 0 until n) {
                val idx = text[i] - 'a'
                while (p!!.children[idx] == null && p != root) {
                    p = p.fail
                }
                p = p.children[idx]
                if (p == null) p = root
                var tmp = p
                while (tmp != root) {
                    if (tmp!!.isEndingChar) {
                        val pos = i - tmp.length + 1
                        action(pos, tmp.strIndex, strs[tmp.strIndex])
                    }
                    tmp = tmp.fail
                }
            }
        }
    }
}

结果

执行用时 : 242 ms, 击败 80.00% 使用 Kotlin 的用户

内存消耗 : 39.90 MB, 击败 60.00% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  List<int> findSubstring(String s, List<String> words) {
    var wordMap = <String, int>{};
    for (String word in words) {
      wordMap.putIfAbsent(word, () => wordMap.length);
    }
    var wordCounts = List<int>.filled(wordMap.length, 0);
    for (String word in words) {
      wordCounts[wordMap[word]!]++;
    }
    var result = <int>[];
    int sLen = s.length;
    int wordNum = words.length;
    int wordLen = words[0].length;
    int len = wordLen * wordNum;
    for (int i = 0; i < wordLen; i++) {
      for (int j = i; j <= sLen - len; j += wordLen) {
        var windowCounts = List<int>.filled(wordMap.length, 0);
        for (int k = wordNum - 1; k >= 0; k--) {
          int begin = j + k * wordLen;
          String word = s.substring(begin, begin + wordLen);
          int index = wordMap[word] ?? -1;
          if (index == -1 || windowCounts[index]++ == wordCounts[index]) {
            j = begin;
            break;
          }
          if (k == 0) {
            result.add(j);
          }
        }
      }
    }
    return result;
  }
}

结果

执行用时 : 821 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 145.20 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func findSubstring(s string, words []string) []int {
    var result []int
    wordMap := make(map[string]int)
    if len(words) == 0 || len(words[0]) == 0 || len(s) < len(words)*len(words[0]) {
        return result
    }
    wordLen, wordNum := len(words[0]), len(words)
    totalLen := wordLen * wordNum
    for _, word := range words {
        wordMap[word]++
    }
    for i := 0; i < wordLen; i++ {
        left, right := i, i
        window := make(map[string]int)
        for right+wordLen <= len(s) {
            currentWord := s[right : right+wordLen]
            right += wordLen
            window[currentWord]++
            for window[currentWord] > wordMap[currentWord] {
                leftWord := s[left : left+wordLen]
                left += wordLen
                window[leftWord]--
            }
            if right-left == totalLen {
                result = append(result, left)
            }
        }
    }
    return result
}

结果

执行用时 : 8 ms, 击败 91.82% 使用 Go 的用户

内存消耗 : 6.72 MB, 击败 33.56% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# @param {String} s
# @param {String[]} words
# @return {Integer[]}
def find_substring(s, words)
  result = []
  word_map = Hash.new(0)
  return result if words.empty? || words[0].empty? || s.length < words.length * words[0].length
  word_len, word_num = words[0].length, words.length
  total_len = word_len * word_num
  words.each { |word| word_map[word] += 1 }
  (0...word_len).each do |i|
    left = i
    right = i
    window = Hash.new(0)
    while right + word_len <= s.length
      current_word = s[right, word_len]
      right += word_len
      window[current_word] += 1
      while window[current_word] > word_map[current_word]
        left_word = s[left, word_len]
        left += word_len
        window[left_word] -= 1
      end
      result << left if right - left == total_len
    end
  end
  result
end

结果

执行用时 : 136 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 208.04 MB, 击败 100.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import scala.collection.mutable.ListBuffer

object Solution {
  def findSubstring(s: String, words: Array[String]): List[Int] = {
    var result = ListBuffer[Int]()
    if (s.isEmpty || words.isEmpty || s.length < words(0).length * words.length) {
      return result.toList
    }
    val wordLen = words(0).length
    val wordNum = words.length
    val totalLen = wordLen * wordNum
    val wordMap = words.groupBy(identity).mapValues(_.length)
    for (i <- 0 until wordLen) {
      var left = i
      var right = i
      var window = scala.collection.mutable.Map[String, Int]().withDefaultValue(0)
      while (right + wordLen <= s.length) {
        val currentWord = s.substring(right, right + wordLen)
        right += wordLen
        window(currentWord) += 1
        while (window(currentWord) > wordMap.getOrElse(currentWord, 0)) {
          val leftWord = s.substring(left, left + wordLen)
          left += wordLen
          window(leftWord) -= 1
        }
        if (right - left == totalLen) {
          result += left
        }
      }
    }
    result.toList
  }
}

结果

执行用时 : 663 ms, 击败 88.89% 使用 Scala 的用户

内存消耗 : 55.71 MB, 击败 88.89% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
impl Solution {
    pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
        use std::collections::HashMap;
        macro_rules! update_diff {
            ($diff:expr, $s:expr, $cnt:expr) => {
                let t = $s as &str;
                *$diff.entry(t).or_insert(0) += $cnt;
                if *$diff.get(t).unwrap() == 0 {
                    $diff.remove(t);
                }
            };
        }
        let mut diff = HashMap::new();
        let (m, n) = (words.len(), words[0].len());
        let mut ans = vec![];
        for idx in 0..n {
            if idx + m * n > s.len() {
                break;
            }
            for i in (idx..idx + m * n).step_by(n) {
                update_diff!(diff, &s[i..i + n], 1);
            }
            for w in words.iter() {
                update_diff!(diff, w, -1);
            }
            if diff.is_empty() {
                ans.push(idx as i32);
            }
            for i in (idx + n..s.len() - m * n + 1).step_by(n) {
                update_diff!(diff, &s[i - n..i], -1);
                update_diff!(diff, &s[i + (m - 1) * n..i + m * n], 1);
                if diff.is_empty() {
                    ans.push(i as i32);
                }
            }
            diff.clear();
        }
        ans
    }
}

结果

执行用时 : 7 ms, 击败 93.94% 使用 Rust 的用户

内存消耗 : 2.39 MB, 击败 84.85% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

暂时未解决

Erlang

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户