6-Line Python Solution O(n^3) Time O(n) Space

  • 1

    The initial value should be set to -1 because (number of cuts) = (number of separated words)-1

    class Solution(object):
        def minCut(self, s):
            f = [-1] + [len(s)-1 for _ in range(len(s))]
            for i in range(len(s)):
                for j in range(i+1,len(s)+1):
                    if s[i:j] == s[i:j][::-1]:
                        f[j] = min(f[j], f[i] + 1)
            return f[-1]

  • 0

    This seems O(n^3) to me because in the inner loop s[i:j] == s[i:j][::-1] takes O(n) time.

  • 1

    Seems you are right

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.