Easy Java Solution, isSubSequence


  • 4

    Idea is sort the dictionary d first by length DESC then lexicographical ASC and test if p is SubSequence of s. The first match is the answer.

    public class Solution {
        public String findLongestWord(String s, List<String> d) {
            if (s.length() == 0 || d.size() == 0) return "";
            
            Collections.sort(d, (a, b) -> {
               if (a.length() != b.length()) return b.length() - a.length();
               return a.compareTo(b);
            });
            
            for (String p : d) {
                if (s.length() < p.length()) continue;
                if (isSubSeq(s, p)) return p;
            }
            
            return "";
        }
        
        private boolean isSubSeq(String s, String p) {
            int i = 0, j = 0;
            while (i < s.length() && j < p.length()) {
                if (s.charAt(i) == p.charAt(j)) {
                    i++; j++;
                }
                else {
                    i++;
                }
            }
            return j == p.length();
        }
    }
    

  • 1
    M

    There is no need to sort the dictionary. We could compare the string with current result during the iteration of the dictionary.

    If sorting the dictionary, let N be the size of dictionary, L be the length of each string in the dictionary, Ls be the length of string s, then the time complexity is
    O(NlgN * L + N * Ls) = O(N(lgN*L + Ls)). (each string comparison will cost O(L) time)
    If without sorting, the time complexity is:
    O(N*L + N * Ls) = O(N(L + Ls))

    The following is my code:

    public class Solution {
        public String findLongestWord(String s, List<String> d) {
            String res = "";
            if (s.length() == 0 || d.size() == 0) {
                return res;
            }
            for (String str : d) {
                int resLen = res.length();
                int strLen = str.length();
                if (isSequence(s, str) &&
                    (strLen > resLen || (strLen == resLen && str.compareTo(res) < 0))) {
                    res = str;
                }
            }
            return res;
        }
        
        private boolean isSequence(String s, String d) {
            int i = 0;
            int j = 0;
            while (i < s.length() && j < d.length()) {
                while (i < s.length() && s.charAt(i) != d.charAt(j)) {
                    i ++;
                }
                if (i < s.length()) {
                    i ++;
                    j ++;
                }
            }
            return j == d.length();
        }
    }
    

  • 0
    A

    said in Easy Java Solution, isSubSequence:

    if (a.length() != b.length()) return b.length() - a.length();

    Could you please explain this part.


  • 1

    @AkshathaNayak We want to sort the dictionary d first by length DESC then lexicographical ASC. Thus if a's length does not equal to b's length, then after sort b will be in front of a.


  • 0
    A

    @shawngao Thanks!


  • 0
    private boolean isSubSeq(String s, String p) {
            int i = 0, j = 0;
            while (i < s.length() && j < p.length()) {
                if (s.charAt(i) == p.charAt(j)) {
                    j++;
                }
                i++;
            }
            return j == p.length();
        }

  • 0
    K

    @shawngao Nice solution. Here's my very clean solution without sorting. Sorting incurs of runtime complexity of at least klog(k), where k is the number of words in the dictionary. My algorithm has a runtime complexity of nk, where n is the number of characters in s.

    public class Solution {
        public String findLongestWord(String s, List<String> d) {
            if (s == null || s.length() == 0 || d == null || d.size() == 0) {
                return "";
            }
            
            String longest = "";
            
            for (String word : d) {
                if (containsSubsequence(s, word) && word.length() >= longest.length()) {
                    if (word.length() > longest.length() || word.compareTo(longest) < 0) {
                        longest = word;
                    }
                }
            }
            
            return longest;
        }
        
        private boolean containsSubsequence(String s, String word) {
            int i = 0;
            for (char c : s.toCharArray()) {
                if (c == word.charAt(i)) {
                    i ++;
                    if (i == word.length()) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.