Broken into extensive use of DS, if its any help to anyone. C# solution


  • 0
    N
        public class Solution {
        public IList<IList<int>> PalindromePairs(string[] words) {
            IList<IList<int>> ret = new List<IList<int>>();
            Dictionary<char, List<string>> startChars = new Dictionary<char, List<string>>();
            Dictionary<char, List<string>> endChars = new Dictionary<char, List<string>>();
            Dictionary<string, int> wordIndex = new Dictionary<string, int>();
            int count = 0;
            bool containsEmpty = false;
            List<string> temp = null;
            List<string> startItems = null;
            List<string> endItems = null;
            List<int> indexes = null;
            
            foreach(var item in words){
                if(item.Length>0){
                    if(startChars.ContainsKey(item[0])){
                        temp = startChars[item[0]];
                        temp.Add(item);
                        startChars[item[0]] = temp;
                    }
                    else{
                        temp = new List<string>();
                        temp.Add(item);
                        startChars[item[0]] = temp;
                    }
                    
                    if(endChars.ContainsKey(item[item.Length-1])){
                        temp = endChars[item[item.Length-1]];
                        temp.Add(item);
                        endChars[item[item.Length-1]] = temp;
                    }
                    else{
                        temp = new List<string>();
                        temp.Add(item);
                        endChars[item[item.Length-1]] = temp;
                    }
                }
                else{
                    containsEmpty = true;
                }
                wordIndex[item] = count++;
            }
            // Console.WriteLine("wordIndex.Count: " + wordIndex.Count + " startChars.Count: " + startChars.Count + " endChars.Count: " + endChars.Count);
            foreach(var item in startChars.Keys){
                if(endChars.ContainsKey(item)){
                    startItems = startChars[item];
                    endItems = endChars[item];
                    foreach(var sItem in startItems){
                        foreach(var eItem in endItems){
                            if(IsPalindrome(sItem, eItem)){
                                int ind1 = wordIndex[sItem];
                                int ind2 = wordIndex[eItem];
                                if(ind1 != ind2){
                                    indexes = new List<int>();
                                    indexes.Add(ind1);
                                    indexes.Add(ind2);
                                    ret.Add(indexes);
                                }
                            }
                        }
                    }
                }
            }
            if(containsEmpty){
                int emptyIndex = wordIndex[""];
                for(int i=words.Length -1 ; i>=0 ; i--){
                    if(IsPalindrome(words[i], "")){
                        indexes = new List<int>();
                        indexes.Add(i);
                        indexes.Add(emptyIndex);
                        ret.Add(indexes);
                        indexes = new List<int>();
                        indexes.Add(emptyIndex);
                        indexes.Add(i);
                        ret.Add(indexes);
                    }
                }
            }
            return ret;
        }
        public bool IsPalindrome(string s1, string s2){
            string s = s1+s2;
            if(s == string.Empty){
                return false;
            }
            int i = 0;
            int j = s.Length-1;
            while(i<j){
                if(s[i] != s[j]){
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }
    }
    

    There are multiple places where code can be improved further for efficiency and it might be missing some good practices. But workable.
    Code seems to be self explanatory, yet, anyone can ask anything if it seems unclear and I'll try to help understand.
    Amortized time complexity is << O(n^2). If someone can prove the time complexity, it would be of help as I am having trouble in attaining tight bound on it.


Log in to reply
 

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