Java DFS+Topology sort solution, 8ms


  • 0
    D
    public class Solution {
        HashMap<Character,Set<Character>> map=new HashMap<>();
        HashSet<Character> visiting=new HashSet<>();
        StringBuffer res=new StringBuffer("");
        boolean cycle=false;
        public String alienOrder(String[] words) {
            for(int i=0;i<words.length-1;i++){
                for(int j=0;j<Math.min(words[i].length(),words[i+1].length());j++){
                    char first=words[i].charAt(j);    
                    char sec=words[i+1].charAt(j);
                    if(!map.containsKey(first)) map.put(first,new HashSet<>());
                    if(!map.containsKey(sec)) map.put(sec,new HashSet<>());
                    if(first!=sec) {
                        map.get(first).add(sec);
                        break;
                    }
                }
            }
            for(String s:words){
                for(char c:s.toCharArray()){
                    if(!map.containsKey(c)) map.put(c,new HashSet<>());
                } 
            }
            while(!cycle&&map.size()!=0) dfs((char)map.keySet().iterator().next());
            return cycle?"":res.toString();
        }
        public void dfs(char key){
            if(cycle||!map.containsKey(key)) return;
            if(visiting.contains(key)){
                cycle=true;return;
            }
            visiting.add(key);
            for(char c:map.get(key)) dfs(c);
            res.insert(0,key);
            visiting.remove(key);
            map.remove(key);
        }
    }
    

Log in to reply
 

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