Does "NRT" have a smaller lexical order than "KUL"?


  • 0
    X

    Hey guys, I failed at the test case below. It seems "NRT" has been considered to have a smaller lexical order than "KUL".
    I got confused about this, I thought 'K' appears before 'N' in alphabet, so "KUL" has smaller lexical order than "NRT". Can anybody help clarify what is the lexical order?

    Input:
    [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
    Output:
    ["JFK","KUL"]
    Expected:
    ["JFK","NRT","JFK","KUL"]

    Below is my code, correct me, thanks in advance.

    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            // add ticket info into the map
            for(String[] ticket: tickets){
                if(map.get(ticket[0]) == null){
                    List<String> des = new ArrayList<String>();
                    des.add(ticket[1]);
                    map.put(ticket[0], des);
                }
                else{
                    List<String> des = map.get(ticket[0]);
                    int index = 0;
                    while(index < des.size()){
                        String curr = des.get(index);
                        if(ticket[1].compareTo(curr) <= 0)
                            break;
                        index++;
                    }
                    des.add(index, ticket[1]);
                }
            }
            
            List<String> result = new ArrayList<String>();
            String start = "JFK";
            result.add(start);
            while(map.get(start) != null && map.get(start).size()>0){
                String des = map.get(start).get(0);
                result.add(des);
                map.get(start).remove(0);
                start = des;
            }
            return result;
        }
    }

  • 0

    @Xulai_Cao You have to arrange all the tickets instead of some of them.


  • 0
    R

    Yes, The questions needs to be more clear about what requirement is when there are dead-end destinations. For example:

    input = [["JFK","KUL"],["JFK","NRT"],["NRT","ABC"],["JFK","TUL"],["JFK","XYZ"]]
    why is this the output: ["JFK","XYZ","TUL","NRT","ABC","KUL"] ?
    My code returns: ["JFK","XYZ","TUL","KUL","NRT","ABC"] which is probably closest to the order expected by other test cases in this problem.
    But still I think the better answer would be: ["JFK","KUL","TUL","XYZ","NRT","ABC"] - cover all deadends first in ASC order, then traverse the others in order.


  • 0

    @rvp said in Does "NRT" have a smaller lexical order than "KUL"?:

    [["JFK","KUL"],["JFK","NRT"],["NRT","ABC"],["JFK","TUL"],["JFK","XYZ"]]

    You cannot really think the test case you mentioned form one valid itinerary here? There is no answer actually, so the answer you get from the OJ is also not what you expected.


Log in to reply
 

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