1408. String Matching in an Array

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.

class Solution {
    public List<String> stringMatching(String[] words) {
        List<String> res = new ArrayList();
        Set<String> set = new HashSet();
        for(int i = 0; i < words.length; i++){
            for(int j = 0; j < words.length; j++){
                if(i == j) continue;
                int l1 = words[i].length(), l2 = words[j].length();
                if(l1 > l2 && issub(words[j], words[i])) set.add(words[j]);
                else if(l2 > l1 && issub(words[i], words[j])) set.add(words[i]);
            }
        }
        res = new ArrayList(set);
        return res;
    }
    public boolean issub(String a, String b){
        int l1 = a.length(), l2 = b.length();
        if(l1 > l2) return issub(b, a);
        for(int i = 0; i <= b.length() - a.length(); i++){
            if(a.equals(b.substring(i, i + a.length()))) return true;
        }
        return false;
    }
}

1. brute force O(n^2)检查俩string是不是谁是谁的substring

查了下，有String.contains() 这个method直接可以查substring。。。

于是：

class Solution {
    public List<String> stringMatching(String[] words) {
        List<String> res = new ArrayList();
        Set<String> set = new HashSet();
        for(int i = 0; i < words.length; i++){
            for(int j = 0; j < words.length; j++){
                if(i == j) continue;
                int l1 = words[i].length(), l2 = words[j].length();
                if(l1 > l2 && words[i].contains(words[j])) set.add(words[j]);
                else if(l2 > l1 && words[j].contains(words[i])) set.add(words[i]);
            }
        }
        res = new ArrayList(set);
        return res;
    }
}

2.也可以先对数组按长短排序，更加简洁

class Solution {
    public List<String> stringMatching(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Set<String> set = new HashSet();
        for (int i = 0; i < words.length-1; i++) {
            for(int j = i+1; j < words.length; j++){
                if(words[j].contains(words[i])) set.add(words[i]);
            }
        }
        return new ArrayList(set);
    }
}