Java Solution with HashMap and TreeSet


  • 0
    L
    public class Solution {
        private boolean canFormat(Map<Character, TreeSet<Integer>> map, String s){
    		int ind = 0;
    		for(char ch : s.toCharArray()){
    			TreeSet<Integer> set = map.get(ch);
    			if(set==null) return false;
    			Integer pos = set.ceiling(ind);
    			if(pos==null) return false;
    			ind = pos + 1;
    		}
    		return true;
    	}
        public String findLongestWord(String s, List<String> d) {
        	Map<Character, TreeSet<Integer>> map = new HashMap<>();
        	for(int i=0;i<s.length();i++){
        		char ch = s.charAt(i);
        		TreeSet<Integer> set = map.getOrDefault(ch, new TreeSet<>());
        		set.add(i);
        		map.put(ch, set);
        	}
        	String res = "";
        	for(String str : d){
        		if((res.equals("") || str.length()>res.length() || (str.length()==res.length() && str.compareTo(res)<0)) && canFormat(map, str)){
        			res = str;
        		}
        	}
            return res;
        }
    }
    

Log in to reply
 

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