Java solution by sorting the list, easy to understand


  • 1
    public class Solution {
        public String findLongestWord(String s, List<String> d) {
            if (d == null || d.size() == 0) return "";
            Collections.sort(d, new Comparator<String>(){
               public int compare(String a, String b) {
                   if (a.length() != b.length()) {
                       return b.length() - a.length();
                   }
                   return a.compareTo(b);
               } 
            });
            
            for (int i = 0; i < d.size(); i++) {
                if (canForm(s, d.get(i))) {
                    return d.get(i);
                }
            }
            return "";
        }
        
        private boolean canForm(String s1, String s2) {
            if (s2.length() > s1.length())  return false;
            
            int i = 0, j = 0;
            while (i < s1.length() && j < s2.length()) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    i++;
                    j++;
                } else {
                    i++;
                }
            }
            return j == s2.length();
        }
    }
    

Log in to reply
 

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