やりたいこと
方法は色々あるとは思いますが、まず思いついたのは下記のように開き括弧をスタックに積んでいく方法です。
- 先頭文字から以下を繰り返す
- 開き括弧の場合はスタックに積んで次の文字へ
- 閉じ括弧の場合はスタックから最後に積んだ開き括弧と比較
- 閉じ括弧と開き括弧が対応していればスタックからpopして次の文字へ
- スタックが空だったり、閉じ括弧と開き括弧が対応していなければ、その時点でfalseを返す
- 最後、開き括弧を積む用のスタックが空だったらtrueを返す
実装
実装はこんな感じ。
class Solution {
public:
bool isValid(string s) {
static const std::unordered_map<char, char> close_to_open {
{ ')', '(' },
{ '}', '{' },
{ ']', '[' },
};
std::stack<char> opens;
for (char c : s) {
if (close_to_open.count(c) == 0) {
opens.push(c);
continue;
}
if (opens.empty() || opens.top() != close_to_open.at(c)) {
return false;
}
opens.pop();
}
return opens.empty();
}
};for 分内のif分岐はネストが深くなるのが嫌という個人的な趣味なのですが、素直に書くならこんな感じ
class Solution {
public:
bool isValid(string s) {
static const std::unordered_map<char, char> close_to_open {
{ ')', '(' },
{ '}', '{' },
{ ']', '[' },
};
std::stack<char> opens;
for (char c : s) {
if (close_to_open.count(c) == 1) {
if (1 <= opens.size() && opens.top() == close_to_open.at(c)) {
opens.pop();
} else {
return false;
}
} else {
opens.push(c);
}
}
return opens.empty();
}
};以上です！