Leetcode 17 Phone Number - using BFS, queue, warmup practice on May 12, 2016

Leetcode17PhoneNumber_UsingBFSQueue

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _17LetterCombinationOfAPhoneNUmber_usingBFSQueue
{
    /*
     * Leetcode 17:
     * Given a digit string, return all possible letter combinations that 
     * the number could represent.
       A mapping of digit to letters (just like on the telephone buttons) is given below.
     * Input:Digit string "23"
       Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
     * 
     * Telephone dial pad:
     *                     0  1   2     3     4     5     6     7      8     9 
     * String[] keyboard={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
     */
    class Solution
    {
        public class Node
        {
            public string phoneStr;
            public int length; 
        }

        static void Main(string[] args)
        {
            IList<string> list = letterCombination("234");
            // test result: "abc", "def", so 3x3 = 9 cases. 
        }

        public static IList<string> letterCombination(string digits)
        {
            IList<string> list = new List<string>();
            if (digits == null || digits.Length == 0)
                return list;

            string[] keyboard = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
            
            buildResult(list, keyboard, digits);  // think about design here

            return list;
        }

        /*
         * Julia's practice on May 12, 2016
         * bfs和dfs都要求写。问时间复杂度是多少，各自的优缺点是啥。
           空间 =>构建过程中bfs比较耗内存，因为要保存一堆中间状态的string；dfs则相对少用些内存。
           时间 => 算清楚string+string和stringbuilder构建新的string时间复杂度有啥区别。
         * 
         */
        private static void buildResult(
            IList<string> list,
            string[] keyboard,
            string digits
            )  // test case: "23", index value 0 and 1
        {
            // need to complete the task using Queue
            if (digits == null || digits.Length == 0)
                return;

            Queue<Node> queue = new Queue<Node>(); 

            // at least one digit in digits string 
            foreach (char c in keyboard[digits[0] - '0'])
            {
                Node node = new Node();

                node.phoneStr = c.ToString();
                node.length   = 1;

                queue.Enqueue(node); 
            }

            while (queue.Count > 0)
            {
                Node node = (Node)queue.Dequeue();

                int    len = node.length;
                string s1  = node.phoneStr; 

                if (digits.Length == len)
                    list.Add(s1);
                else
                {
                    // continue to append the string 
                    foreach (char c in keyboard[digits[len] - '0'])
                    {
                        string newS1 = s1 + c.ToString(); 

                        Node newNode = new Node();

                        newNode.phoneStr = newS1;
                        newNode.length   = len + 1;

                        queue.Enqueue(newNode); 
                    }
                }
            }

            return; 
        }
    }
}