Given an array of string words. Return all strings in words which is a substring of another word in any order.
String words[i] is a substring of words[j], it can be obtained removing some characters to the left and/or right side of words[j].
Example 1:
Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is a substring of "mass" and "hero" is a 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.Solution:
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode.AskGif.Easy.String
{
class StringMatchingArray
{
public void execute()
{
string[] words = new string[] { "mass", "as", "hero", "superhero" };
var res = StringMatching(words);
}
public IList<string> StringMatching(string[] words)
{
//to Store unique solution.
var ListStr = new HashSet<string>();
for (int i = 0; i < words.Length-1; i++)
{
for(int j = i+1; j < words.Length; j++)
{
string subStr;
if (words[i].Length>words[j].Length)
subStr = ReturnSubstring(words[i], words[j]);
else
subStr = ReturnSubstring(words[j], words[i]);
if (subStr != null)
ListStr.Add(subStr);
}
}
var result = new List<string>();
foreach (var item in ListStr)
{
result.Add(item);
}
return result;
}
private string ReturnSubstring(string word1, string word2)
{
for (int i = 0; i < word1.Length-word2.Length+1; i++)
{
for (int j = 0; j < word2.Length; j++)
{
if (word1[i + j] != word2[j])
break;
if (j == word2.Length - 1)
{
return word2;
}
}
}
return null;
}
}
}
Time Complexity: O(n^2) for comparing character by character
Space Complexity: O(n) for storing in Linked list and returning in result
