使用Java计算最长平衡括号前缀的长度

在本文中，我们将探讨如何使用Java查找最长平衡括号前缀的长度，首先我们将通过一些示例来理解问题，然后学习两种不同的方法来找到它。

问题陈述

在这里，我们将得到一个包含括号的字符串，我们需要找到字符串中平衡括号集的长度，即对于每个左括号"("，如果存在一个右括号")"，则我们称之为平衡的。

前缀定义字符串中的第一个平衡集，例如括号集'(())()'，我们只考虑'(())'。

输入输出场景

让我们看一些输入输出场景，以便更好地理解。

  • 假设输入字符串为"(()"，这里平衡括号前缀为()，则长度为2。
  • 如果输入字符串为"((()()))((("，这里平衡括号前缀为((()()))，则长度为8。
  • 如果输入字符串为"(()())()()"，平衡括号前缀为(()())，则长度为6。

我们可以得到最长平衡括号前缀的长度：

  • 使用栈数据结构
  • 计算左括号和右括号

使用栈数据结构

我们可以使用一个栈，然后从栈中，如果我们得到一个左括号'('，则将其压入栈中，如果我们得到一个右括号，则弹出栈并使计数器变量加2（一个平衡对的长度为2），继续这个过程，当我们得到空栈时，我们将返回计数器变量。

算法

以下是算法：

Step 1: Initialize a stack and a counter.
Step 2: Iterate through each character in the string.

If character is ( push it onto the stack.
If character is ) pop the stack.
Increment counter by 2
Check whether the stack is empty or not
If empty, break;

Step 3: Finally return the counter;

示例

Open Compiler
import java.util.Stack;

public class Example {
   public static int longestBalancedPrefix(String s) {
      Stack<Character> stack = new Stack<>();
      int count = 0;
      for (int i = 0; i < s.length(); i++) {
         char ch = s.charAt(i);
         if (ch == '(') {
            stack.push(ch);
         } else if (ch == ')') {
            if (!stack.isEmpty()) {
               stack.pop();
               count += 2;
               if (stack.isEmpty()) {
                  break;
               }
            }
         }
      }
      return count;
   }

   public static void main(String args[]) {
      String s = "((())((";
      System.out.println("input string is: " + s);
      System.out.println("Length of longest balanced parentheses prefix is " + longestBalancedPrefix(s));
   }
}

输出

input string is: ((())((
Length of longest balanced parentheses prefix is 4

Learn Java in-depth with real-world projects through our Java certification course. Enroll and become a certified expert to boost your career.

计算左括号和右括号

在这种方法中，我们将使用两个变量，一个为count，另一个为length。然后从字符串中，如果字符为"("，我们将count加1，如果字符为")"，我们将count减1，并将length加2，并检查count是否为零，如果为零，则中断循环并返回length。

示例

Open Compiler
public class Example {
   public static void main(String args[]) {
      String s = "((())())(())";
      int count = 0;
      int length = 0;
      for (int i = 0; i < s.length(); i++) {
         char ch = s.charAt(i);
         if (ch == '(') {
            count++;
         } else if (ch == ')') {
            count--;
            length = length + 2;
            if (count == 0) {
               break;
            }
         }
      }
      System.out.println("Input string is " + s);
      System.out.println("Length of the longest balanced parentheses prefix is " + length);
   }
}

输出

Input string is ((())())(())
Length of the longest balanced parentheses prefix is 8

更新于：2024年11月7日

29 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告