[leetcode] Longest Word in Dictionary through Deleting

problem

code

1st try: Time Limit Exceeded

class Solution {
    public String findLongestWord(String s, List<String> d) {
        int sLen = s.length();
        if (sLen == 0) return "";
        // new RegExp(b.charAt(0) + ".*", "gi");
        
        Collections.sort(d);
        
        int dLen = d.size();
        String answer = "";
        for (String str : d) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < str.length() - 1; i++) {
                sb.append(str.charAt(i));
                sb.append(".*");
            }
            sb.append(str.charAt(str.length() - 1));
            Pattern p = Pattern.compile(sb.toString());
            Matcher m = p.matcher(s);

            if (m.find()) {
                if (answer.length() < str.length())
                    answer = str;
            }
        }
        
        return answer;
        
    }
}

2nd try

class Solution {
    // O(X); x is an average string length
    public boolean isSubsequence(String str, String s) {
        int j = 0;
        for (int i = 0; i < s.length() && j < str.length(); i++)
            if (str.charAt(j) == s.charAt(i))
                j++;
        return j == str.length();
    }

    public String findLongestWord(String s, List<String> d) {
        // sort: O(nlogn), compare string: x(average string length) => xnlogn; => O(x*nlogn)
        Collections.sort(d, new Comparator<String>() {
            public int compare(String o1, String o2) {
                // == lexicographical order, != descending order
                return o1.length() == o2.length() ? o1.compareTo(o2) : o2.length() - o1.length();
            }
        });

        for (String str : d)
            if (isSubsequence(str, s))
                return str;

        return "";
    }
}

Time: O(XNlogN + XN)
Space: O(1)

• sorting the list of strings, d, in a descending order depeding on length and in a lexicographical order if the length of both are equal.

• leetcode

public class Solution {
    public boolean isSubsequence(String x, String y) {
        int j = 0;
        for (int i = 0; i < y.length() && j < x.length(); i++)
            if (x.charAt(j) == y.charAt(i))
                j++;
        return j == x.length();
    }
    public String findLongestWord(String s, List < String > d) {
        String max_str = "";
        for (String str: d) {
            if (isSubsequence(str, s)) {
                if (str.length() > max_str.length() || (str.length() == max_str.length() && str.compareTo(max_str) < 0))
                    max_str = str;
            }
        }
        return max_str;
    }
}

Time: O(X*N)
Space: O(X), X is an array of chars;