1408 - String Matching in an Array

Given an array of string words, return all strings in words that is a substring of another word. You can return the answer in any order.

A substring is a contiguous sequence of characters within a string

 Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []
Explanation: No string of words is substring of another string.

 Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 30
• words[i] contains only lowercase English letters.
• All the strings of words are unique.

Solution 1: Brute Force Enumeration

C++

• class Solution {
  public:
      vector<string> stringMatching(vector<string>& words) {
          vector<string> ans;
          int n = words.size();
          for (int i = 0; i < n; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (i != j && words[j].find(words[i]) != string::npos) {
                      ans.push_back(words[i]);
                      break;
                  }
              }
          }
          return ans;
      }
  };

JAVA

• class Solution {
      public List<String> stringMatching(String[] words) {
          List<String> ans = new ArrayList<>();
          int n = words.length;
          for (int i = 0; i < n; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (i != j && words[j].contains(words[i])) {
                      ans.add(words[i]);
                      break;
                  }
              }
          }
          return ans;
      }
  }

PYTHON

• class Solution:
      def stringMatching(self, words: list) -> list:
          ans = []
          n = len(words)
          for i in range(n):
              for j in range(n):
                  if i != j and words[i] in words[j]:
                      ans.append(words[i])
                      break
          return ans