LeetCode-678.:有効なかっこ文字列(Valid Parenthesis String)
2792 ワード
タイトルの説明
3つの文字しか含まれていない文字列:(,)と*を指定し、この文字列が有効な文字列であるかどうかを確認するために関数を書きます.有効な文字列には、次のルールがあります.左かっこ(対応する右かっこが必要です). 任意の右かっこ)には、対応する左かっこ(. )が必要です.左かっこ(対応する右かっこの前にある必要があります). 空の文字列も有効な文字列とみなされます.
例1:
例2:
例3:
注意:
文字列サイズは[1100]の範囲内になります.
構想
この問題の主な考え方は、2つの配列で保存することです.ある場合は、(記号が一致してから記号と一致し、最後に(余分な*数の場合は必ず不正であり、小さい場合は一致する*が存在するかどうかを判断します.すなわち、各(記号にはその文字の後ろに存在する*記号が1つ必要です.
コード#コード#
3つの文字しか含まれていない文字列:(,)と*を指定し、この文字列が有効な文字列であるかどうかを確認するために関数を書きます.有効な文字列には、次のルールがあります.
*
は、単一の右かっこ、または単一の左かっこ(、または空の文字列)とみなすことができる.例1:
: "()"
: True
例2:
: "(*)"
: True
例3:
: "(*))"
: True
注意:
文字列サイズは[1100]の範囲内になります.
構想
この問題の主な考え方は、2つの配列で保存することです.ある場合は、(記号が一致してから記号と一致し、最後に(余分な*数の場合は必ず不正であり、小さい場合は一致する*が存在するかどうかを判断します.すなわち、各(記号にはその文字の後ろに存在する*記号が1つ必要です.
コード#コード#
bool checkValidString(char* s) {
int len = strlen(s);
int* stack1 = (int *)malloc(sizeof(int) * len);
int* stack2 = (int *)malloc(sizeof(int) * len);
int index1 = 0;
int index2 = 0;
int ans = 0;
for(int i = 0;i < len;i++){
if(s[i] == '(')
stack1[index1++] = i;
else if(s[i] == '*')
stack2[index2++] = i;
else{
if(index1 != 0)
index1--;
else if(index2 != 0)
index2--;
else if(index1 == 0 && index2 == 0)
ans = 1;
}
}
if(index2 >= index1){
for(;index1 > 0;index1--,index2--){
if(stack2[index2 - 1] < stack1[index1 - 1]){
ans = 1;
break;
}
}
}
else
return false;
if(ans == 1)
return false;
return true;
}