比较字符串时的算法复杂性，而某些字符可能是用正则表达式定义的

Question

我创建了一个算法来检查匹配的字符串，因为某些字符可能是由“*”或“.”定义的正则表达式。我正在尝试分析它的复杂性；但是我看不出这个递归函数的大 O 到底是什么。

该算法将 2 个字符串作为输入，returns 如果一个字符串可以与第二个字符串匹配，则为布尔值。

Example:

A = "abc"
B = "ab*"
Output = true

A = "ab."
B = "abc"
Output = true

A = "abcd*"
B = "ab"
Output = false



public static boolean match(String a, String b) {
        //Check if a == b , if so, strings match
        if (a.equals(b))
            return true;
        //Check if second char in a in an asterisk,  return true if substring of b matches b.
        if (hasAsterisk(a) && match(a.substring(2), b))
            return true;
        //Check if second char of b is an asterisk, return true if substring of b matches a.
        if (hasAsterisk(b) && match(a, b.substring(2)))
            return true;
        //Check if a and b is not empty
        if (!a.isEmpty() && !b.isEmpty()) {
            //Check if first char of a is asterisk, if so match a substring with b
            if (a.charAt(0) == '*')
                return match(a.substring(1), b);
            //Check if first char of b is asterisk, if so match b substring with a
            if (b.charAt(0) == '*')
                return match(a, b.substring(1));
            //Check if first char of a or b is "DOT(.)", if so match substrings.
            return charMatch(a.charAt(0), b.charAt(0)) 
                    && match(a.substring(1), b.substring(1));
        }
        //If not match, return false
        else 
            return false;

    }

    private static boolean hasAsterisk(String a) {
        return a.length() > 1 && a.charAt(1) == '*';
    }

    private static boolean charMatch(char a, char b) {
        return a == b || a == '.' || b == '.';
    }

我的后续问题是，如何运行更有效？

谢谢！

Answer 1

如果你追求 Big O 复杂性，那么它是 O(n)，那是因为你的每个循环（在 eqauls()、match() 等...）增加了它执行的比较次数随着字符串中字符数的增加。为简单起见，我假设两个输入字符串的长度大致相同，因此 n 是第一个字符串还是第二个字符串的长度并不重要。

如果你想提高你的大 O 复杂性，坏消息是你做不到。如果你仔细想想，你会意识到在最坏的情况下（字符串匹配到最后一个字符）不可能在不至少比较每个字符一次的情况下执行这些比较。因此 O(n).

您可以通过不重复相同的比较多次来提高实际的比较次数。您的代码中有很多。

比较字符串时的算法复杂性，而某些字符可能是用正则表达式定义的

Algorithm complexity while comparing strings while some characters might be defined with regular expressions

algorithm

big-o

time-complexity