1408. String Matching in an Array - Explanation

1. Brute Force

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        res = []

        for i in range(len(words)):
            for j in range(len(words)):
                if i == j:
                    continue

                if words[i] in words[j]:
                    res.append(words[i])
                    break

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2 * m ^ 2)$
Space complexity:
- $O(1)$ extra space.
- $O(n * m)$ space for the output list.

Where $n$ is the number of words, and $m$ is the length of the longest word.

2. Sorting

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        res = []
        words.sort(key=len)

        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if words[i] in words[j]:
                    res.append(words[i])
                    break

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2 * m ^ 2)$
Space complexity:
- $O(1)$ or $O(n)$ depending on the sorting algorithm.
- $O(n * m)$ space for the output list.

Where $n$ is the number of words, and $m$ is the length of the longest word.

3. Knuth-Morris-Pratt (KMP) Algorithm

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        def kmp(word1: str, word2: str) -> int:
            lps = [0] * len(word2)
            prevLPS, i = 0, 1

            while i < len(word2):
                if word2[i] == word2[prevLPS]:
                    lps[i] = prevLPS + 1
                    prevLPS += 1
                    i += 1
                elif prevLPS == 0:
                    lps[i] = 0
                    i += 1
                else:
                    prevLPS = lps[prevLPS - 1]

            i = j = 0
            while i < len(word1):
                if word1[i] == word2[j]:
                    i += 1
                    j += 1
                else:
                    if j == 0:
                        i += 1
                    else:
                        j = lps[j - 1]

                if j == len(word2):
                    return i - len(word2)

            return -1

        res = []
        words.sort(key=len)

        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if kmp(words[j], words[i]) != -1:
                    res.append(words[i])
                    break

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2 * m)$
Space complexity:
- $O(m)$ extra space.
- $O(1)$ or $O(n)$ space depending on the sorting algorithm.
- $O(n * m)$ space for the output list.

Where $n$ is the number of words, and $m$ is the length of the longest word.

4. Rabin-Karp Algorithm (Rolling Hash)

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        def rabinKarp(word1: str, word2: str) -> int:
            base1, mod1 = 31, 768258391
            base2, mod2 = 37, 685683731
            n, m = len(word1), len(word2)

            power1, power2 = 1, 1
            for _ in range(m):
                power1 = (power1 * base1) % mod1
                power2 = (power2 * base2) % mod2

            word1_hash1 = word1_hash2 = 0
            word2_hash1 = word2_hash2 = 0

            for i in range(m):
                word1_hash1 = (word1_hash1 * base1 + ord(word2[i])) % mod1
                word1_hash2 = (word1_hash2 * base2 + ord(word2[i])) % mod2
                word2_hash1 = (word2_hash1 * base1 + ord(word1[i])) % mod1
                word2_hash2 = (word2_hash2 * base2 + ord(word1[i])) % mod2

            for i in range(n - m + 1):
                if word2_hash1 == word1_hash1 and word2_hash2 == word1_hash2:
                    return i

                if i + m < n:
                    word2_hash1 = (word2_hash1 * base1 - ord(word1[i]) * power1 + ord(word1[i + m])) % mod1
                    word2_hash2 = (word2_hash2 * base2 - ord(word1[i]) * power2 + ord(word1[i + m])) % mod2

                    word2_hash1 = (word2_hash1 + mod1) % mod1
                    word2_hash2 = (word2_hash2 + mod2) % mod2

            return -1

        res = []
        words.sort(key=len)

        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if rabinKarp(words[j], words[i]) != -1:
                    res.append(words[i])
                    break

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2 * m)$
Space complexity:
- $O(1)$ or $O(n)$ space depending on the sorting algorithm.
- $O(n * m)$ space for the output list.

Where $n$ is the number of words, and $m$ is the length of the longest word.

5. Z-Algorithm

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        def zAlgorithm(word1: str, word2: str) -> int:
            s = word2 + "$" + word1
            n = len(s)
            z = [0] * n
            l, r = 0, 0

            for i in range(1, n):
                if i <= r:
                    z[i] = min(r - i + 1, z[i - l])
                while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                    z[i] += 1
                if i + z[i] - 1 > r:
                    l, r = i, i + z[i] - 1

            for i in range(len(word2) + 1, n):
                if z[i] == len(word2):
                    return i - len(word2) - 1

            return -1

        res = []
        words.sort(key=len)

        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if zAlgorithm(words[j], words[i]) != -1:
                    res.append(words[i])
                    break

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2 * m)$
Space complexity:
- $O(m)$ extra space.
- $O(1)$ or $O(n)$ space depending on the sorting algorithm.
- $O(n * m)$ space for the output list.

Where $n$ is the number of words, and $m$ is the length of the longest word.

6. Trie

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.cnt = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert_suffixes(self, word: str) -> None:
        for i in range(len(word)):
            node = self.root
            for j in range(i, len(word)):
                idx = ord(word[j]) - ord('a')
                if not node.children[idx]:
                    node.children[idx] = TrieNode()

                node = node.children[idx]
                node.cnt += 1

    def search(self, word: str) -> bool:
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            node = node.children[idx]
        return node.cnt > 1

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        res = []
        trie = Trie()

        for word in words:
            trie.insert_suffixes(word)

        for word in words:
            if trie.search(word):
                res.append(word)

        return res

Time & Space Complexity

Time complexity: $O(n * m ^ 2)$
Space complexity:
- $O(n * m ^ 2)$ extra space.
- $O(n * m)$ space for the output list.

Where $n$ is the number of words, and $m$ is the length of the longest word.