Day10 daily 3 questions (3): String Matching in array

subject ：

Here's an array of strings words , Each string in the array can be regarded as a word . Please press arbitrarily Sequential return words All words that are substrings of other words in .

If you can delete words[j]  Leftmost and / Or the rightmost characters get word[i] , So the string words[i] Namely words[j] A substring of .

Example 1：

Input ：words = [“mass”,“as”,“hero”,“superhero”]
Output ：[“as”,“hero”]
explain ：“as” yes “mass” Substring of ,“hero” yes “superhero” Substring of .
[“hero”,“as”] It's also a valid answer .
Example 2：

Input ：words = [“leetcode”,“et”,“code”]
Output ：[“et”,“code”]
explain ：“et” and “code” All are “leetcode” Substring of .
Example 3：

Input ：words = [“blue”,“green”,“bu”]
Output ：[]

Tips ：

1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] Contains only lowercase English letters .
Subject data Guarantee Every words[i] They are unique .
adopt

Ideas ：

Double traversal , Minimize the number of inner layer traversal .

java Code ：

class Solution {
    public List<String> stringMatching(String[] words) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < words.length-1; i++) {
            for (int j = i+1; j < words.length; j++) {
                if (!res.contains(words[j]) && words[i].contains(words[j])) {
                    res.add(words[j]);
                } else if (!res.contains(words[i]) && words[j].contains(words[i])) {
                    res.add(words[i]);
                }
            }
        }

        return res;
    }
}