My Java solution is accepted, but I wonder if how I can make it short


  • 0
    V
    public class Solution {
        public String alienOrder(String[] words) {
            StringBuilder sb = new StringBuilder();
            Map<Character,List<Character>> relations = calculateRelations(words);
            Set<Character> allCharSet = getAllChars(words);//a hashset
            while(true){
                Set<Character> childrenSet = getChildrenSet(relations, allCharSet);
                if (childrenSet.isEmpty()) break;
                Set<Character> currentTopLevelSet = new HashSet(allCharSet);
                currentTopLevelSet.removeAll(childrenSet);
                if (currentTopLevelSet.isEmpty()) return "";
                appendToSb(sb,currentTopLevelSet);
                allCharSet.removeAll(currentTopLevelSet);
            }
            appendToSb(sb,allCharSet);
            return sb.toString();
        }
    
        private void appendToSb(StringBuilder sb, Set<Character> charSet) {
            for (char c:charSet) {
                sb.append(c);
            }
        }
    
        private Set<Character> getChildrenSet(Map<Character,List<Character>> relations, Set<Character> chars) {
            Set<Character> set = new HashSet<>();
            for (Character c:chars) {
                if (relations.containsKey(c)) {
                    set.addAll(relations.get(c));
                }
            }
            return set;
        }
    
        private Set<Character> getAllChars(String[] words) {
            Set<Character> set = new HashSet<>();
            for (String word:words) {
                for (char c : word.toCharArray()){
                    set.add(c);
                }
            }
            return set;
        }
    
        private Map<Character,List<Character>> calculateRelations(String[] words) {
            Map <Character,List<Character>> map = new HashMap<>();
            for (int i=0;i<words.length-1;i++) {
                String word0=words[i];
                String word1=words[i+1];
                for (int j=0;j<Math.min(word0.length(),word1.length());j++) {
                    if (word0.charAt(j)!=word1.charAt(j)){
                        if (map.containsKey(word0.charAt(j))){
                            map.get(word0.charAt(j)).add(word1.charAt(j));
                        }else{
                            List<Character> charList = new ArrayList<>();
                            charList.add(word1.charAt(j));
                            map.put(word0.charAt(j), charList);
                        }
                    break;
                    }
                }
            }
            return map;
        }
    }

Log in to reply
 

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