Java 12ms solution using a the best-first DFS


  • -1
    B

    public class Solution {

    private int length;
    private HashMap<String, ArrayList<String>> ticketMap = new HashMap<String, ArrayList<String>>();
    
    public List<String> findItinerary(String[][] tickets) {
        
        length = tickets.length + 1;
        
        for (String[] trip : tickets)
        {
            if (ticketMap.containsKey(trip[0]))
            {
                ticketMap.get(trip[0]).add(trip[1]);
            }
            else
            {
                ArrayList<String> arr = new ArrayList<String>();
                arr.add(trip[1]);
                ticketMap.put(trip[0], arr);
            }
        }
        
        for (ArrayList<String> value : ticketMap.values()) {
            Collections.sort(value);
        }
        
        ArrayList<String> itinerary = new ArrayList<String>();
        itinerary.add("JFK");
       
        search("JFK", itinerary);
        
        return itinerary;
    }
    
    public boolean search(String start, ArrayList<String> itinerary)
    {
        if (itinerary.size() == length)
            return true;
        ArrayList<String> arr = ticketMap.get(start);
        if (arr != null)
        {//it's OK to continue
            for (int i = 0; i < arr.size(); ++i)
            {
                String end = arr.get(i);
                itinerary.add(end);
                arr.remove(i);
                if (search(end, itinerary) == false)
                {
                    //undo the move
                    itinerary.remove(itinerary.size() - 1);
                    arr.add(i, end);
                }
                else
                {
                    return true;
                }
            }
            return false;
        }
        else
        {
            return false;
        }
    }
    

    }


  • 0
    H

    Hi, I have a question about this part of the code:
    for (int i = 0; i < arr.size(); ++i)
    {
    String end = arr.get(i);
    itinerary.add(end);
    arr.remove(i);
    if (search(end, itinerary) == false)
    {
    //undo the move
    itinerary.remove(itinerary.size() - 1);
    arr.add(i, end);
    }
    .....

    when I change the code to:

    for( String end : list){
    // String end = list.get(i);
    res.add(end);
    int x = list.indexOf(end);
    list.remove(end);

          if(dfs(res, map, num) == false){
              res.remove(res.size() - 1);
              list.add(x, end);
    

    .....
    There is an error:
    Runtime Error Message:
    Line 46: java.util.ConcurrentModificationException

    Actually, the latter the what I wrote before I saw your solution. When I change that part, my code works. Can any one tell me why : ( I think they basically do the same thing. Besides, when we remove string from the arr, how i keep changing during this process?


  • 0
    B

    I think maybe it's because that you use list.indexOf(end); since there can be equivalent string in the same list. The function indexOf will always gives you the first element. For example if we have a list of ['A', 'A', 'B', 'C'], when the loop goes to the second 'A', my function will remove the second one, while your code will remove the first 'A', then it will cause the error. Sorry for my bad English, hope it answers your question.


  • 0
    Z

    I think problem is that you used the wrong Remove method in Java List. You should be very carefully doing remove operation when you are traversing this list. The security and correct method is using Iterator to traverse the list and remove elements. There will be problems if you use index or for( String end : list) to traverse a list and remove its elements.


Log in to reply
 

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