Re: [閒聊] 每日leetcode

[DJYOSHITAKA (franchouchouISBEST)]

678. Valid Parenthesis String
補昨天的
用兩個stack 一個for左括 一個for星星
遇到右括優先pop左括 再來pop星星
過了第一段後確保沒有右括號
再來處理多的左括號
用了一堆if醜醜的
對不起

bool checkValidString(string s) {
    stack<int> par;
    stack<int> star;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i] == '(')
        {
            par.push(i);
        }
        else if(s[i] == ')')
        {
            if(!par.empty())
            {
                par.pop();
            }
            else if(star.empty())
            {
               return false;
            }
            else
            {
                star.pop();
            }
        }
        else
        {
            star.push(i);
        }
    }

    while(!par.empty())
    {
        if(star.empty())
        {
            return false;
        }
        else if(par.top() > star.top())
        {
            return false;
        }
        else
        {
            star.pop();
            par.pop();
        }
    }

    return true;
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.137.162 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712583485.A.FBF.html
推 sustainer123: 大師
推 RinNoKareshi: 大師