Longest Word in Dictionary through Deleting

https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/description/

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Thoughts

思路很直观，对d中的每个string判断是否是s的subsequent。e如果出现在了s中，则e[i] = s[j]且对对于e[i-1] = s[j - c], j > j - c, 所以判断时用两个指针，依次找e中的每个字符是否按序出现在了s中。

Code

class Solution {
    public String findLongestWord(String s, List<String> d) {
        int longest = 0;
        String res = "";
        for (String e : d) {
            if (e.equals("")) {
                continue;
            }
            int i = 0, j = 0;

            while (i < e.length() && j < s.length()) {
                if (s.charAt(j) == e.charAt(i)) {
                    i++;
                }
                j++;
            }

            if (i == e.length()) {
                if (e.length() > longest) {
                    longest = e.length();
                    res = e;
                } else if (e.length() == longest && e.charAt(0) < res.charAt(0)) {
                    res = e;
                } 
            }
        }
        return res;
    }
}

Analysis

Errors:

1. 还是用while好实现俩指针算法。

做题耗时20min

时间复杂度O(kn), k为d的长度，n为s的长度。