[Solved] Given an array of string words. Return all strings in words which is substring of another word in any order. String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

Question

Given an array of string words. Return all strings in words which is substring of another word in any order. 

String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

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: []

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 30
  • words[i] contains only lowercase English letters.
  • It’s guaranteed that words[i] will be unique.

Python Solution

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        words.sort(key=len)
        res=[]
        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
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 514

Leave a Reply

Your email address will not be published. Required fields are marked *