Leetcode – Number of Strings That Appear as Substrings in Word Solution

Substrings and string matching are essential topics in computer science and software engineering, often appearing in various forms across different applications, from search engines to bioinformatics. The problem titled “Number of Strings That Appear as Substrings in Word” from Leetcode offers a unique twist on these classical themes. This problem can be solved through multiple approaches, each offering its own advantages and disadvantages. In this extensive guide, we’ll discuss the problem statement, various solutions, their time complexities.

Problem Statement

Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in word.

A substring is a contiguous sequence of characters within a string.

The objective is to find the count of strings in the given patterns array that appear as substrings in the word word.

The Basic Approach: Brute-force Substring Matching

The simplest way to approach this problem is by checking each string in patterns to see if it appears as a substring in word. Python’s in keyword makes this extremely straightforward.

Python Code

def numOfStrings(patterns, word):
    count = 0
    for pattern in patterns:
        if pattern in word:
            count += 1
    return count

Time Complexity

The time complexity for this approach is O(n×m), where n is the length of the word, and m is the total length of all strings in the patterns array. This could be quite inefficient for very long words or a large number of patterns.

Optimized Approach: Using Trie Data Structure

A Trie (pronounced “try”) is a tree-like data structure that is used to store a dynamic set of strings. Tries are particularly useful for implementations that require fast lookups, like this one.

Python Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def buildTrie(patterns):
    root = TrieNode()
    for pattern in patterns:
        node = root
        for ch in pattern:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
    return root

def searchTrie(root, word):
    count = 0
    for i in range(len(word)):
        node = root
        for j in range(i, len(word)):
            if word[j] in node.children:
                node = node.children[word[j]]
                if node.is_end:
                    count += 1
                    node.is_end = False  # To avoid counting duplicates
            else:
                break
    return count

def numOfStrings(patterns, word):
    root = buildTrie(patterns)
    return searchTrie(root, word)

Time Complexity

The time complexity for building the Trie is O(m), where m is the total length of all strings in the patterns array. The time complexity for the search operation is O(n), where n is the length of the word. So, the overall time complexity would be O(n+m).

Conclusion

The “Number of Strings That Appear as Substrings in Word” problem is an intriguing problem that allows us to explore multiple techniques, such as brute-force string matching and Trie data structures. Each approach offers its own benefits, either in simplicity or in efficiency.