Stupid Straightforward Union-Find Method


  • 0
    public String alienOrder(String[] words) {
        Map<String, List<Character>> lookup = new HashMap<>();
        List<Character> result = new LinkedList<>();
        for (int wi = 0; wi < words.length; wi++) {
            String word = words[wi];
            Character firstChar = word.charAt(0);
            if (!result.contains(firstChar)) result.add(firstChar);
            for (int ci = 1; ci <= word.length(); ci++) {
                String key = word.substring(0, ci);
                String value = word.substring(ci);
                if (!lookup.containsKey(key))
                    lookup.put(key, new ArrayList<>());
                if (!lookup.get(key).contains(value) && value.length() > 0)
                    lookup.get(key).add(value.charAt(0));
            }
        }
    
        Map<Character, Set<Character>> union = new HashMap<>();
        Set<Character> set = new HashSet<>(result);
        for (Character c : result) union.put(c, set);
    
        for (List<Character> list : lookup.values()) {
            for (int i = 0; i <= list.size() - 2; i++) {
                Character c1 = list.get(i);
                Character c2 = list.get(i + 1);
                if (!result.contains(c1)) result.add(c1);
                if (!result.contains(c2)) result.add(c2);
    
                // switch, if needed
                int c1i = result.indexOf(c1);
                int c2i = result.indexOf(c2);
                if (c1i > c2i) {
                    result.remove(c1);
                    result.add(c2i, c1);
                }
    
                // union
                if (!(union.containsKey(c1) || union.containsKey(c2))) {
                    union.put(c1, new HashSet<>());
                    union.put(c2, union.get(c1));
                    union.get(c1).add(c1);
                    union.get(c1).add(c2);
                } else if (union.containsKey(c1)) {
                    union.get(c1).add(c2);
                    union.put(c2, union.get(c1));
                } else if (union.containsKey(c2)) {
                    union.get(c2).add(c1);
                    union.put(c1, union.get(c2));
                }
            }
        }
    
        if (new HashSet<>(union.values()).size() > 1) return "";
    
        StringBuilder builder = new StringBuilder();
        for (Character c : result) builder.append(c);
        return builder.toString();
    }

  • 0

    The union part can be replaced by a char[] :)
    When I have time, I will rewrite one.


Log in to reply
 

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