C# recursion and stack solution


  • 0
    Y
    public class Solution {
        public string DecodeString(string s) {
            if(string.IsNullOrEmpty(s)||s.IndexOf('[')==-1)
                return s;
            //recrusive solution
            Stack<int> indStack=new Stack<int>();
            int sInd=0,eInd=0,i=0,n=s.Length;
            for(;i<n;i++)
            {
                if(s[i]=='[')
                    indStack.Push(i);
                else if(s[i]==']')
                {
                    if(indStack.Count>1)
                        indStack.Pop();
                    else
                    {
                        sInd=indStack.Pop();
                        eInd=i;
                        //getnumbers
                        int num = 0,t=sInd-1;
                        for(;t>=0;t--)
                        {
                            if(!(s[t]-'0'>=0 && s[t]-'0'<=9))
                                break;
                        }
                        num=int.Parse(s.Substring(t+1,sInd-t-1));
                        StringBuilder sb=new StringBuilder();
                        //first part
                        sb.Append(s.Substring(0,t + 1));
                        //decode part
                        string decode=DecodeString(s.Substring(sInd+1,eInd-sInd-1));
                        for(int q=0;q<num;q++)
                            sb.Append(decode);
                        //second part
                        sb.Append(s.Substring(eInd+1,s.Length-1-eInd));
                        s = sb.ToString();
                        i = t + num*decode.Length;
                        n = s.Length;
                    }
                }
            }
            
            return s;
        }
        
    }

Log in to reply
 

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