京东笔试：合法字符串

题目描述

有关合法字符串的问题，记不太清了，大概描述如下：

• 首先​

  ​""​

  ​是合法的字符串
• 如果​

  ​X​

  ​​是合法的字符串，那么​

  ​(X)​

  ​也是合法的字符串
• 如果​

  ​X​

  ​​是合法的字符串，那么​

  ​XY​

  ​也是合法的字符串

比如​

​""，()，()()，(((())))，((),())​

​​都是合法的字符串

现在，我们要对合法字符串进行删除，一次删除如下：

• 首先去掉最左边的​

  ​"("​

  ​
• 然后去掉一个​

  ​")"​

  ​

如果执行一次操作后，字符串依旧是合法的，那么就认为操作成功。

现在，给你一个合法字符串，问可以有多少种删除方法。

举例子：

1、​

​()()()()​

​​ 只有 1 种方法。因为去掉最左边的​

​(​

​​ 后，字符串变为​

​)()()()​

​​ ，接下来只能删除第一个​

​")"​

​​。然后继续删除左边第一个​

​(​

​。。。所以只有一种方法。

2、​

​(((())))​

​​ 有24种方法。首先去掉最左边的​

​(​

​​ 后，字符串变为​

​((())))​

​​，接下来我们可以删除右边任意一个​

​)​

​，这里就有4种删法。同理，下一次有3种删法，就是4 * 3 * 2 * 1 = 24种。

思路：

设定两个变量temp和result，初始temp = 0，result = 1

接下来向后扫描字符串，如果遇到：

• ‘(‘，则temp++
• ‘)’，则result *= temp，并且temp–

最后返回result。

import java.util.Scanner;

public class Main

    public static int solution(String line) {
        int len = line.length();
        int temp = 0;
        int result = 1;
        for(int i = 0; i < len; i++) {
            if(line.charAt(i) == '(') {
                temp++;
            }else if(line.charAt(i) == ')') {
                result *= temp;
                --temp;
            }
        }
        return result;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String line = sc.nextLine();
            System.out.println(solution(line));
        }
        sc.close();
    }

}