[leetcode] 1408. String Matching in an Array

Question

Given an array that contains some words. You should return all the string that is part of other strings. The order does not matter.

• 1408. String Matching in an Array

Solution

You can solve by using in statement. This statement can check whether a word is contained in an array. Pick up the string from the array and compare others string in the array. If you want to implement efficiently, you should sort the array before checking. Then, pick up the string from the left of the array and compare the all strings that is located at right side from the chosen string. Time complexity is same but this way usually has good performance.

Submission

Here is result.

Runtime: 28 ms, faster than 98.64% of Python3 online submissions for String Matching in an Array.
Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for String Matching in an Array.

Time complexity: O(n^2 * s) s is the maximum length of the array
Space complexity: O(1)

This code has loop inside loop, so time complexity is gonna be O(n^2). Also, the each elements are checked. So, if the maximum length is defined as s, total time complexity is gonna be O(n^2*s).

Space complexity is for return array. So, this is gonna be O(n).

Here is my python code.

# witout sorting
# Time complexity: O(n^2*S)
# Space complexity: O(n)
def stringMatching(self, words: List[str]) -> List[str]:
    res: List[str] = []
    for i in range(len(words)):
        for j in range(len(words)):
            if i != j and words[i] in words[j]:
                res.append(words[i])
                break
    return res

# sorting
# Time complexity: O(nlogn + n^2*S) -> O(n^2*S)
# Space complexity: O(n)
def stringMatching(self, words: List[str]) -> List[str]:
    words.sort(key=len)
    res: List[str] = []
    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