Java two solutions, beat 95%+


  • 0
    F

    Solution1: Sort dictionary words

    class MyCompare implements Comparator<String> {
    	public int compare(String s1, String s2) {
    		return s2.length() == s1.length() ? s1.compareTo(s2)
    				: s2.length() - s1.length();
    	}
    }
    public String findLongestWord(String s, List<String> d) {
    	Collections.sort(d, new MyCompare());
    	for (String word : d) {
    		char[] cs = word.toCharArray();
    		int index = -1;
    		boolean match = true;
    		for (char c : cs) {
    			index = s.indexOf(c, index + 1);
    			if (index < 0) {
    				match = false;
    				break;
    			}
    		}
    		if (match)
    			return word;
    	}
    	return "";
    }
    

    Solution2: no sorting

    public String findLongestWord(String s, List<String> d) {
    	String longest = "";
    	for (String dictWord : d) {
    		char[] cs = dictWord.toCharArray();
    		int index = -1;
    		boolean match = true;
    		for (char c : cs) {
    			index = s.indexOf(c, index + 1);
    			if (index < 0) {
    				match = false;
    				break;
    			}
    		}
    		if (match) {
    			if (dictWord.length() > longest.length()
    					|| dictWord.length() == longest.length()
    							&& dictWord.compareTo(longest) < 0)
    				longest = dictWord;
    		}
    	}
    	return longest;
    }

Log in to reply
 

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