java - 这个重复子串模式代码的运行时和空间复杂度是多少？（代码是用Java编写的）

Question

我为 LeetCode #459 问题编写了这个解决方案。https://leetcode.com/problems/repeated-substring-pattern/ 我想知道这个解决方案的运行时间和空间复杂度。我假设 O(logN N) 的运行时复杂度，其中 N 是字符串的长度。我对吗？

    
    public boolean repeatedSubstringPattern(String s) {
        if (s == null || s.isEmpty()) return true;
        int l = s.length();
        for (int i = l / 2; i > 0; --i) {
            if (l % i == 0 && isThisSubString(s, s.substring(0, i), l / i)) {
                return true;
            }
        }
        return false;
    }
    
      private boolean isThisSubString(String s, String subString, int m) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; ++i) {
            sb.append(subString);
        }
        return s.equals(sb.toString());
    }

}

标签： javastringdata-structurestime-complexityspace-complexity

Answer 1

在最坏的情况下，当 i 为 1 时，m 等于 5。isThisSubString 方法将遍历整个字符串。所以在最坏的情况下渐近，它是 O(n^2)。