C# recursive solution


  • 1
    M
    public class Solution {
    private IDictionary<string, List<string>> m_routes;
        private int m_count;
    
    	public IList<string> FindItinerary(string[,] tickets)
    	{
    		m_routes = new Dictionary<string, List<string>>();
    		m_count = tickets.GetLength(0);
    		for (int i = 0; i < m_count; i++)
    		{
    			var s = tickets[i, 0];
    			var d = tickets[i, 1];
    
    			if (!m_routes.ContainsKey(s))
    				m_routes.Add(s, new List<string>());
    
    			m_routes[s].Add(d);
    		}
    
    		foreach (var list in m_routes.Values)
    			list.Sort();
    
    		return GetPath("JFK");
    	}
    
        private IList<string> GetPath(string s)
        {
    	    if (m_routes.ContainsKey(s) && m_routes[s].Count > 0)
    	    {
    		    var children = m_routes[s];
    		    for (int i = 0; i < children.Count; i++)
    		    {
    			    var child = children[i];
    			    children.RemoveAt(i);
    			    m_count--;
    
    			    var best = GetPath(child);
    			    children.Insert(i, child);
    				m_count++;
    
    				if (best != null)
    			    {
    				    best.Insert(0, s);
    				    return best;
    			    }
    		    }
    
    		    return null;
    	    }
    	    
    		if (m_count == 0)
    		    return new List<string> {s};
    	
    		return null;
        }
    }

  • 0
    C

    Revised to avoid to be challenged on OO

            public  IList<string> FindItinerary(string[,] tickets)
            {
                int cnt;
                IDictionary<string, List<string>> paths;
                paths = new Dictionary<string, List<string>>();
                cnt = tickets.GetLength(0);
                for (int i = 0; i < cnt; i++)
                {
                    var s = tickets[i, 0];
                    var d = tickets[i, 1];
    
                    if (!paths.ContainsKey(s))
                        paths.Add(s, new List<string>());
    
                    paths[s].Add(d);
                }
    
                foreach (var list in paths.Values)
                    list.Sort();
    
                return GetPath("JFK", cnt, paths);
            }
    
            private IList<string> GetPath(string s, int cnt, IDictionary<string, List<string>> paths)
            {
                if (paths.ContainsKey(s) && paths[s].Count > 0)
                {
                    var children = paths[s];
                    for (int i = 0; i < children.Count; i++)
                    {
                        var child = children[i];
                        children.RemoveAt(i);
                        cnt--;
    
                        var best = GetPath(child, cnt, paths);
                        children.Insert(i, child);
                        cnt++;
    
                        if (best != null)
                        {
                            best.Insert(0, s);
                            return best;
                        }
                    }
    
                    return null;
                }
    
                if (cnt == 0)
                    return new List<string> { s };
    
                return null;
            }
    

  • 0

    No idea why this code got AC. Obviously try test case [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"]], it should output ["JFK","MUC","LHR"] instead of null.


Log in to reply
 

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