LeetCode.1249 移除无效的括号

C# 可变字符串

C#中常用的字符串string是字符串常量类似于Java，通过+=等获得的新字符串会生成新的字符串，而不是直接在原来的字符串上修改，所以执行效率会比较慢。如果要使用可变字符串，可以使用StringBuilder类，也可以使用List代替字符串，然后转为字符串，下面为LeetCode一道例题。

1249. 移除无效的括号

思路

有效括号经典问题，由于是只有一种括号，所以可以不使用栈而是用计数变量来代替。
过程中其他的字符均添加到新的字符串中，括号进行额外判断，根据是否合法决定是否要添加到字符串中。
如果最后计数变量不为零，则倒序删除若干个左括号。
也可以通过对括号的对数进行计数，再进行一次添加到新字符串。

代码

1. 使用StringBuilder类

public class Solution {
    public string MinRemoveToMakeValid(string s) {
        StringBuilder tmp = new StringBuilder("");
        int cnt = 0, cnt2 = 0;
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                if (cnt >= 0) {
                    cnt++;
                    tmp.Append(s[i]);
                }
            } else if (s[i] == ')') {
                if (cnt > 0) {
                    cnt--;
                    tmp.Append(s[i]);
                    cnt2++;
                }
            } else {
                tmp.Append(s[i]);
            }
        }
        if (cnt == 0) {
            return tmp.ToString();
        }
        StringBuilder ans = new StringBuilder("");
        for (int i = 0; i < tmp.Length; i++) {
            if (cnt2 == 0 && tmp[i] == '(') {
                continue;
            }
            ans.Append(tmp[i]);
            if (tmp[i] == '(') {
                cnt2--;
                cnt--;
            } else if (tmp[i] == ')') {
                cnt--;
            } 
        }
        // while (cnt > 0) {
        //     cnt--;
        //     ans = ans.Remove(ans.LastIndexOf('('), 1);
        // }
        return ans.ToString();
    }
}

2. 使用List类代替字符串

public class Solution {
    public string MinRemoveToMakeValid(string s) {
        List<char> tmp = new List<char>();
        int cnt = 0, cnt2 = 0;
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                if (cnt >= 0) {
                    cnt++;
                    tmp.Add(s[i]);
                }
            } else if (s[i] == ')') {
                if (cnt > 0) {
                    cnt--;
                    tmp.Add(s[i]);
                    cnt2++;
                }
            } else {
                tmp.Add(s[i]);
            }
        }
        if (cnt == 0) {
            return new string(tmp.ToArray());
        }
        List<char> ans = new List<char>();
        for (int i = 0; i < tmp.Count; i++) {
            if (cnt2 == 0 && tmp[i] == '(') {
                continue;
            }
            ans.Add(tmp[i]);
            if (tmp[i] == '(') {
                cnt2--;
                cnt--;
            } else if (tmp[i] == ')') {
                cnt--;
            } 
        }
        // while (cnt > 0) {
        //     cnt--;
        //     ans = ans.Remove(ans.LastIndexOf('('), 1);
        // }
        return new string(ans.ToArray());
    }
}

3. 直接使用string类，效率极低

public class Solution {
    public string MinRemoveToMakeValid(string s) {
        string ans = "";
        int cnt = 0;
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                if (cnt >= 0) {
                    cnt++;
                    ans += s[i];
                }
            } else if (s[i] == ')') {
                if (cnt > 0) {
                    cnt--;
                    ans += s[i];
                }
            } else {
                ans += s[i];
            }
        }
        // 亲测，对于string类，使用删除字符不会超时但效率极低，使用重新添加会超时
        while (cnt > 0) {
            cnt--;
            ans = ans.Remove(ans.LastIndexOf('('), 1);
        }
        return ans;
    }
}