説明#
'('、')'、'{'、'}'、'['、']' のみを含む文字列が与えられた場合、文字列が有効かどうかを判断します。
有効な文字列は以下の条件を満たす必要があります：
- 左括弧は対応する右括弧で閉じる必要があります。
- 左括弧は正しい順序で閉じる必要があります。
空の文字列は有効な文字列と見なされます。
例 1:
入力: "()"
出力: true
例 2:
入力: "()[]{}"
出力: true
例 3:
入力: "(]"
出力: false
例 4:
入力: "([)]"
出力: false
例 5:
入力: "{[]}"
出力: true
アプローチ#
- 最初に思いついたのは、スタックの push と pop 操作を利用する方法です。左括弧は push し、右括弧は pop します。pop 時に右括弧とスタックのトップの左括弧が一致しない場合は false を返します。
- 文字列をループし終えた後、スタックの長さが 0 であれば true、そうでなければ false を返します。
void push(char* dir,int* now_size,char get) {
int size = *now_size;
for(;size;size--)
dir[size] = dir[size - 1];
dir[size] = get;
(*now_size)++;
}
void pop(char* dir,int* now_size) {
for(int i=0;i<(*now_size);i++)
dir[i] = dir[i + 1];
dir[*now_size] == '\0';
(*now_size)--;
}
bool isValid(char * s){
if(*s == '\0')//空文字列はtrueを返す
return true;
char get[10000] = "\0";
int size = 0;
for(int i=0;s[i] != '\0';i++) {
if(s[i] == '(' || s[i] == '[' || s[i] == '{')
push(get,&size,s[i]);
else {
if(s[i] - get[0] < 3 && s[i] - get[0] > 0)//括弧が一致する
pop(get,&size);
else
return false;
}
}
if(size != 0)
return false;
return true;
}
- 文字列の長さが不明なため、スタックの長さを非常に大きく設定し、手順もやや煩雑です
改良したアプローチ#
- 文字列自体を使用し、追加のメモリを使用せずにスタックのような操作を行います
- 左括弧に出会った場合は何もせず、右括弧に出会った場合は前の括弧が一致するかどうかを調べ、一致する場合は 2 つの括弧を消去し、一致しない場合は false を返します。前の括弧が見つからない場合は false を返します。
- ループ中に左括弧の数を記録し、括弧を消去する過程で減算します。ループが終了した後、左括弧の数が 0 でない場合は false を返し、0 の場合は true を返します。
bool isValid(char * s){
if(*s == '\0')//空文字列はtrueを返す
return true;
int left = 0;
for(int i = 0;s[i] != '\0';i++) {
if(s[i] == ')' || s[i] == ']' || s[i] == '}') { //右括弧を検出して消去を開始
for(int j = i - 1;j >= -1;j--) {
if(j == -1) //前の括弧が見つからない場合
return false;
if(s[j] != '\0' && j >= 0) { //前の括弧を検出
if(s[i] - s[j] < 3 && s[i] - s[j] > 0) {//前の括弧と現在の括弧が一致する場合
left--; //左括弧の数を減算
s[i] = s[j] = '\0'; //括弧を消去
break;
}
else //前の括弧と現在の括弧が一致しない場合
return false;
}
}
}
else left++; //左括弧の数を増加
}
if(left)
return false;
return true;
}
- まあまあかなと思いますが、実行時間はまだ長いです。後で最適化します。