fb phone希望印度姐姐手下留情

watercup 发表于 2017-11-8 11:28
发个java的解法，只扫描一遍，用stack存储invalid括号的位置，最后把invalid的括号删除就可以了

public  ...

            sb.deleteCharAt(stack.pop());
每call 一次 deletecharAt api 貴啊... worst case O(n) 每次操作

一个for loop， two pointers？

感谢楼主分享 加油！

watercup 发表于 2017-11-8 11:28
发个java的解法，只扫描一遍，用stack存储invalid括号的位置，最后把invalid的括号删除就可以了

public  ...

非常感谢你的思路！但是我想跟你讨论一下，这样的做法虽然保证了只有一次for loop，但是StringBuilder.deleteAt()每次都是O(n)的操作吧？就其实这样one pass的做法，一般情况下时间是要比two passes的长的？不知道我这样考虑对不对，如果有错误麻烦指正。谢谢啦～

觉得用stack 的方法 比较clean。或者，这么写也行。

    String removeParentheses(String input, char[] p) {
        int l =0;
        StringBuilder sb = new StringBuilder();
        for (int i =0; i<input.length(); i++) {
            if (input.charAt(i) == p[0]) {
                l++;
            } else if (input.charAt(i) == p[1]) {
                l--;
            }
            if (l<0) {
                l++;
            } else {
                sb.append(input.charAt(i));
            }
        }
        if (l != 0) {
            return new StringBuilder(removeParentheses(sb.reverse().toString(), new char[]{')', '('})).reverse().toString();
        }
        return sb.toString();
    }

sparrow52 发表于 2017-12-25 07:40
非常感谢你的思路！但是我想跟你讨论一下，这样的做法虽然保证了只有一次for loop，但是StringBuilder.de ...

对于这个问题，我觉得如何返回这个valid的字符串不是考察的重点.  对于StringBuilder，deleteAt的内部使用的System.arraycopy, 这是一个native的API，通常认为这个native的方法还是挺快的。

string parath(string para){
    string res="";
    stack<char>st;
    for(int i=0;i<para.size();i++){
        if(para[i]!=')') st.push(para[i]);
        else{
            int j=i;
            while(para[j]==')') j++;
            int count=j-i;
            string tmp="";
            while(!st.empty()&&count){
                if(st.top()=='(') {
                    st.pop();
                    tmp="("+tmp;
                    count--;
                }
                else {
                    tmp=st.top()+tmp;
                    st.pop();
                }
            }
            tmp+=string(j-i-count,')');
            res+=tmp;
        }
    }
    return res;   
}