Not sure if the test case is right. Any explanation?


  • 0
    H

    I don't get the test case:
    Input: ["aac","aabb","aaba"]
    Expected: "cba"

    My output is "acb".

    public class Solution {
        public String alienOrder(String[] words) {
            if (words == null || words.length == 0) {
                return null;
            }
        
            LinkedList<Character> order = new LinkedList<>();
        
            String first = words[0];
            for(int i=0; i<first.length(); i++) {
                if (!order.contains(first.charAt(i))) {
                    order.add(first.charAt(i));
                }
            }
        
            return orderWords(words, order);
        }
    
        private String orderWords(String[] words, LinkedList<Character> orderList) {
            int validIndex = 0;
            for(int i=1; i<words.length; i++) {
                int index = -1;
                String word = words[i];
                for(int j=word.length()-1; j >= 0; j--) {
                    if (!orderList.contains(word.charAt(j))) {
                        if (index == -1) {
                            orderList.add(word.charAt(j));
                        } else {
                            if (index <= validIndex) {
                                return "";
                            }
                            orderList.add(index, word.charAt(j));
                        }
                    }
                    index = orderList.indexOf(word.charAt(j));
                    if (index < validIndex) {
                    	return "";
                    }
                }
                validIndex = index;
            }
        
            StringBuffer sb = new StringBuffer();
            for(char c : orderList) {
            	sb.append(c);
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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