467. Unique Substrings in Wraparound String

Link: https://leetcode.com/problems/unique-substrings-in-wraparound-string/?tab=Description

Consider the stringsto be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", soswill look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another stringp. Your job is to find out how many unique non-empty substrings ofpare present ins. In particular, your input is the stringpand you need to output the number of different non-empty substrings ofpin the strings.

Note:pconsists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input:
 "a"

Output:
 1

Explanation:
 Only the substring "a" of string "a" is in the string s.

Example 2:

Input:
 "cac"

Output:
 2

Explanation:
 There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

Input:
 "zab"

Output:
 6

Explanation:
 There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

Time Limited Exceeded

Solution:

Two dimensional DP: f[left][right] = f[left][right - 1] and (ord(p[right - 1]) + 1 == ord(p[right]) or p[right - 1] == 'z' and p[right] == 'a')

class Solution(object):
    def findSubstringInWraproundString(self, p):
        """
        :type p: str
        :rtype: int
        """
        if not p:
            return 0

        p_len = len(p)

        # init checking table
        checking_table = [[False for _ in xrange(p_len)] for _ in xrange(p_len)]
        for left in xrange(p_len):
            for right in xrange(p_len):
                if left >= right:
                    checking_table[left][right] = True

        for left in xrange(p_len):
            for right in xrange(left + 1, p_len):
                checking_table[left][right] = checking_table[left][right - 1] and\
                                              ((ord(p[right - 1]) + 1 == ord(p[right])) or\
                                               (p[right - 1] == 'z' and p[right] == 'a'))

        sub_p_set = set()
        counter = 0
        for left in xrange(p_len):
            for right in xrange(left, p_len):
                sub_p = p[left:right + 1]

                if sub_p not in sub_p_set and checking_table[left][right]:
                    sub_p_set.add(sub_p)
                    counter += 1

        return counter

Time Limited Exceeded

class Solution(object):
    def findSubstringInWraproundString(self, p):
        """
        :type p: str
        :rtype: int
        """
        if not p:
            return 0

        counter = 0
        sub_p_set = set()
        p_len = len(p)
        for left in xrange(p_len):
            for right in xrange(left, p_len):
                sub_p = p[left:right + 1]
                if sub_p not in sub_p_set and self.is_valid(sub_p):
                    sub_p_set.add(sub_p)
                    counter += 1

        return counter

    def is_valid(self, sub_p):
        if not sub_p:
            return False

        prev_c = sub_p[0]
        for i in xrange(1, len(sub_p)):
            curr_c = sub_p[i]

            if not ((ord(prev_c) + 1 == ord(curr_c)) or (prev_c == 'z' and curr_c == 'a')):
                return False

            prev_c = curr_c

        return True