Solution to exit earlier unless the worst case


  • 0
        public string[] FindRestaurant(string[] list1, string[] list2) {
            if(list1.Length > list2.Length)
            {
                return FindRestaurant(list2, list1);
            }
            
            List<string> rs = new List<string>();
            Dictionary<string, int> dic = new Dictionary<string, int>();
            int minSum = list1.Length + list2.Length - 2;
            for(int i = 0; i< list1.Length; i++)
            {
                if(i > minSum) return rs.ToArray();
                if(dic.ContainsKey(list1[i]))
                {
                    if(dic[list1[i]] + i > minSum)continue;
                    if(dic[list1[i]] + i == minSum)rs.Add(list1[i]);
                    if(dic[list1[i]] + i < minSum)
                    {
                        rs = new List<string>();
                        minSum = dic[list1[i]] + i;
                        rs.Add(list1[i]);
                    }
                }
                else
                {
                    dic.Add(list1[i], i);
                }
                
                if(dic.ContainsKey(list2[i]))
                {
                    if(dic[list2[i]] + i > minSum)continue;
                    if(dic[list2[i]] + i == minSum)rs.Add(list2[i]);
                    if(dic[list2[i]] + i < minSum)
                    {
                        rs = new List<string>();
                        minSum = dic[list2[i]] + i;
                        rs.Add(list2[i]);
                    }
                }
                else
                {
                    dic.Add(list2[i], i);
                }
            }
            
            
            for(int i = list1.Length; i< list2.Length; i++)
            {
                if(i > minSum) return rs.ToArray();
               
                if(dic.ContainsKey(list2[i]))
                {
                    if(dic[list2[i]] + i > minSum)continue;
                    if(dic[list2[i]] + i == minSum)rs.Add(list2[i]);
                    if(dic[list2[i]] + i < minSum)
                    {
                        rs = new List<string>();
                        minSum = dic[list2[i]] + i;
                        rs.Add(list2[i]);
                    }
                }
            }
            return rs.ToArray();
        }

Log in to reply
 

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