Valid Parenthesis String
2020/4/16
問題概要
(*))みたいなカッコとアスタリスクが渡されたとして、(が)より前にあり、かつその数が釣り合うか判定せよ
ただし*は打ち消し文字、もしくは空白として都合よくみなせる
解法
(が来たら水位low, highはともに上がる
)が来たら水位low, highはともに下がる
()みたいな正しい組が現れたら、low, highは両方0
*が来たら、3パターン想定する
()は釣り合ってるのでスペースとみなすパターン
(を打ち消すパターン
low--
これで打ち消しきればlow == 0となるはずなので、low = max(low, 0)としてlowを更新
こうすることで、打ち消してもなお(が多いならlow == 0が成立しないはず。
)を打ち消すパターン
high++
これで打ち消してもなお)が多いなら、high < 0となるはずなので判定でfalse。
考えてみれば、この水位を常にバランスさせるみたいな考え方は(その都度最善手を選び続けるので)貪欲法だなーと思った 計算量はO(N)
code:solution.cpp
class Solution {
public:
bool checkValidString(string s) {
int low = 0, high = 0;
for (char c : s) {
if (c == '(') {
low++;
high++;
} else if (c == ')') {
low--;
high--;
} else {
low--;
high++;
}
// ')'が一つでも多ければここで引っかかる
if (high < 0) return false;
// '*'を考慮してもなお'('が多ければ、
// lowは0より大きくなるし、
// '*'や')'によりlowが0未満になれば0がlowに採用される
low = max(low, 0);
}
return low == 0;
}
};