20有効なカッコJava
leetcode 20有効かっこ
タイトルの説明
‘(’,’)’,’{’,’}’,’[’,’]’のみを含む文字列を与え,文字列が有効であるか否かを判断する.
有効な文字列は次のとおりです.左かっこは、同じタイプの右かっこで閉じる必要があります. 左かっこは正しい順序で閉じなければなりません.注意空の文字列は有効な文字列とみなされます.
アルゴリズムの考え方
法一:この方法は、文字列から「()」、「{}」、「[]」を空の文字列「」で置き換え続ける限り、置き換えられないときに残りの文字列が空であるかどうかを判断し、空であれば一致することを理解しやすい.
法二:スタックを使用して実現し、文字列の文字を遍歴し、左カッコに遭遇すると右カッコをスタックに入れ、右カッコに遭遇するとスタックの一番上にポップアップされた要素と比較し、異なると一致せず、すべての文字を遍歴するまで、スタックが空であれば一致しない.
コード実装
法一
法二
タイトルの説明
‘(’,’)’,’{’,’}’,’[’,’]’のみを含む文字列を与え,文字列が有効であるか否かを判断する.
有効な文字列は次のとおりです.
アルゴリズムの考え方
法一:この方法は、文字列から「()」、「{}」、「[]」を空の文字列「」で置き換え続ける限り、置き換えられないときに残りの文字列が空であるかどうかを判断し、空であれば一致することを理解しやすい.
法二:スタックを使用して実現し、文字列の文字を遍歴し、左カッコに遭遇すると右カッコをスタックに入れ、右カッコに遭遇するとスタックの一番上にポップアップされた要素と比較し、異なると一致せず、すべての文字を遍歴するまで、スタックが空であれば一致しない.
コード実装
法一
public class Solution {
public static void main(String args[]) {
System.out.println(isValid("{}{{[[()]]}}"));
}
public static boolean isValid(String s) {
// "()","[]","{}", ,
if (s.contains("()") || s.contains("[]") || s.contains("{}")) {
return isValid(s.replace("()", "").replace("[]", "").replace("{}", ""));
} else {
return "".equals(s);
}
}
}
法二
import java.util.Stack;
public class Solution {
public static void main(String args[]) {
System.out.println(isValid("{}{{[[()]]}}"));
}
public static boolean isValid(String s) {
// , , , 。
Stack<Character>stack = new Stack<Character>();
for(char c: s.toCharArray()){
if(c=='(')stack.push(')');
else if(c=='[')stack.push(']');
else if(c=='{')stack.push('}');
else if(stack.isEmpty()||c!=stack.pop())return false;
}
return stack.isEmpty();
}
}