问答

当前位置
  • 首页
  • 问答
  • 780. Remove Invalid Parentheses DFS的时间复杂度

780. Remove Invalid Parentheses DFS的时间复杂度

  • Ta: laq

这道题在LC上看到下面的DFS解法,貌似比BFS的O(n*2^n)的复杂度要低很多,但是不是很明白怎么分析它的时间复杂度。请老师们帮忙分析一下。还有这道题好像还挺高频的,不知道如果被面到该回答DFS还是BFS呢?

public List<String> removeInvalidParentheses(String s) {
    List<String> ans = new ArrayList<>();
    remove(s, ans, 0, 0, new char[]{'(', ')'});
    return ans;
}

public void remove(String s, List<String> ans, int last_i, int last_j,  char[] par) {
    for (int stack = 0, i = last_i; i < s.length(); ++i) {
        if (s.charAt(i) == par[0]) stack++;
        if (s.charAt(i) == par[1]) stack--;
        if (stack >= 0) continue;
        for (int j = last_j; j <= i; ++j)
            if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))
                remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);
        return;
    }
    String reversed = new StringBuilder(s).reverse().toString();
    if (par[0] == '(') // finished left to right
        remove(reversed, ans, 0, 0, new char[]{')', '('});
    else // finished right to left
        ans.add(reversed);
}

2 个回复

2018-04-08 恒助教

DFS和BFS的时间复杂度是一样的,他们的不同仅仅在于对于每一个点的遍历方式不一样


2018-04-09 白助教

是这样的, BFS枚举了所有的可能子串,所以是稳定的O(n*2^n).
DF'S 在枚举的时候只找可能需要删除的情况,对于一定不需要删除的不考虑。所以复杂度在一般情况下会比BFS来的快,但是极端情况下也必须枚举完所有的情况。
因此这个理论复杂度我们还是只能认为是O(n*2^n)

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1