C# - iterative backtracking - in order tree traversal - collect leaves


  • 0

    This problem is like a tree problem. At each letter you can either choose to flip it so it becomes part of a count or leave it as is. In this sense each node can be split into a 2 nodes, 1 that is unchanged and one that flips the letter at it's index to be replaced along with it's flipped neighbors with a number.

    For example: input = "abcdef" after some moves becomes "a###e#" would form an abbreviation = "a3e1"

    The tree starts to look like this

                        "abcdef"
          "abcdef"                 "#bcdef"
    "abcdef"    "a#cdef"      "#bcdef"  "##cdef"    
    

    Here I use a char array and when I "flip" a letter I replace it with '#'. The tree can be thought of as going left means the string is unchanged, and going right the letter at that index is flipped. When you hit a leaf you want to capture this abbreviation.

    The tricky part is that when you "visit" the node you need to do the backtracking, which in this case means reverting the tail from the index onward back to the original characters.

        public IList<string> GenerateAbbreviations(string word) 
        {
            IList<string> list = new List<string>();
            Stack<int> stack = new Stack<int>();
            int index = 0;
            char[] chars = word.ToCharArray();
            
            while (index < chars.Length || stack.Count > 0)
            {
                if (index < chars.Length)
                {
                    // go left
                    stack.Push(index);
                    index++;
                }
                else
                {
                    index = stack.Pop();
                    if (index == chars.Length - 1) list.Add(Make(chars));  // collect leaf
                    
                    // backtrack - revert tail
                    for (int i = index + 1; i < chars.Length; i++) chars[i] = word[i];
                    
                    chars[index] = '#';   // go right
                    if (index == chars.Length - 1) list.Add(Make(chars));  // collect leaf
                    
                    index++;
                }
            }
            
            if (word.Length == 0) list.Add("");
            return list;
        }
        
        public string Make(char[] word)
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < word.Length; i++)
            {
                int num = 0;
                while (i < word.Length && word[i] == '#')
                {
                    num++;
                    i++;
                }
                
                if (num == 0) sb.Append(word[i]);
                else { sb.Append(num); i--; }
            }
            return sb.ToString();
        }
    

Log in to reply
 

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