Java移除無效括號的方法實現

Posted on by

一、題目

給你一個由 ‘(‘、’)’ 和小寫字母組成的字符串 s。

你需要從字符串中刪除最少數目的 ‘(‘ 或者 ‘)’ （可以刪除任意位置的括號)，使得剩下的「括號字符串」有效。

有效「括號字符串」應當符合以下 任意一條 要求：

空字符串或隻包含小寫字母的字符串
可以被寫作 AB（A 連接 B）的字符串，其中 A 和 B 都是有效「括號字符串」
可以被寫作 (A) 的字符串，其中 A 是一個有效的「括號字符串」

二、示例

))((  -》  

(leetode  -》  leetode
leetode)  -》  leetode

(lee(to)de  -》  lee(to)de
lee(to)de)  -》  lee(to)de

(lee(t(c)o)de  -》  lee(t(c)o)de
lee(t(c)o)de)  -》  lee(t(c)o)de

三、解法1

public class Test {

 public static void main(String[] args) {
  String s1 = "))((";
  System.out.println(s1 + "  -》  " + minRemoveToMakeValid(s1));

  String s2 = "(leetode";
  System.out.println(s2 + "  -》  " + minRemoveToMakeValid(s2));

  String s3 = "leetode)";
  System.out.println(s3 + "  -》  " + minRemoveToMakeValid(s3));

  String s4 = "(lee(to)de";
  System.out.println(s4 + "  -》  " + minRemoveToMakeValid(s4));

  String s5 = "lee(to)de)";
  System.out.println(s5 + "  -》  " + minRemoveToMakeValid(s5));

  String s6 = "(lee(t(c)o)de";
  System.out.println(s6 + "  -》  " + minRemoveToMakeValid(s6));

  String s7 = "lee(t(c)o)de)";
  System.out.println(s7 + "  -》  " + minRemoveToMakeValid(s7));
 }

 public static String minRemoveToMakeValid(String str) {
  // 初始化"("和")"的個數為0
  int left = 0;
  int right = 0;

  // 將字符串轉換為char數組
  char[] chars = str.toCharArray();

  // 從左到右標記多餘的")"右括號
  for (int i = 0; i < chars.length; i++) {
   if (chars[i] == '(') {
    left++;
   } else if (chars[i] == ')') {
    right++;
   }

   if (right > left) {
    chars[i] = '#';

    left = right = 0;
   }
  }

  left = right = 0;

  // 從右到左標記多餘的"("左括號
  for (int i = chars.length - 1; i >= 0; i--) {
   if (chars[i] == '(') {
    left++;
   } else if (chars[i] == ')') {
    right++;
   }

   if (right < left) {
    chars[i] = '#';

    left = right = 0;
   }
  }

  return String.valueOf(chars).replaceAll("#", "");
 }
}

四、解法2

Stack.peek 與Sstack.pop 的區別

  • 相同點：大傢都返回棧頂的值。
  • 不同點：peek 不改變棧的值(不刪除棧頂的值)，pop會把棧頂的值刪除。
public class Test {

 public static void main(String[] args) {
  String s1 = "))((";
  System.out.println(s1 + "  -》  " + minRemoveToMakeValid(s1));

  String s2 = "(leetode";
  System.out.println(s2 + "  -》  " + minRemoveToMakeValid(s2));

  String s3 = "leetode)";
  System.out.println(s3 + "  -》  " + minRemoveToMakeValid(s3));

  String s4 = "(lee(to)de";
  System.out.println(s4 + "  -》  " + minRemoveToMakeValid(s4));

  String s5 = "lee(to)de)";
  System.out.println(s5 + "  -》  " + minRemoveToMakeValid(s5));

  String s6 = "(lee(t(c)o)de";
  System.out.println(s6 + "  -》  " + minRemoveToMakeValid(s6));

  String s7 = "lee(t(c)o)de)";
  System.out.println(s7 + "  -》  " + minRemoveToMakeValid(s7));
 }

 public static String minRemoveToMakeValid(String str) {
  // 記錄要刪除括號的下標，然後從後往前刪除坐標
  StringBuffer result = new StringBuffer(str);
  
  Stack<Integer> stack = new Stack<>();
  ArrayList<Integer> deleteRes = new ArrayList<>();
  
  for (int i = 0; i < str.length(); i++) {
   if (str.charAt(i) == '(') {
    stack.push(i);
   } else if (str.charAt(i) == ')') {
    if (stack.empty()) {
     deleteRes.add(i);
    } else if (str.charAt(stack.peek()) == '(') {
     stack.pop();
    }
   }
  }
  
  while (!stack.empty()) {
   int temp = stack.peek();
   stack.pop();
   deleteRes.add(0, temp);
  }
  
  deleteRes.sort(Integer::compareTo);
  
  for (int i = deleteRes.size() - 1; i >= 0; i--) {
   result.deleteCharAt(deleteRes.get(i));
  }
  
  return result.toString();
 }
}

到此這篇關於Java移除無效括號的方法實現的文章就介紹到這瞭,更多相關Java移除無效括號內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：