回文子字符串的数目

发表于 | 更新于 | 分类于

回文子字符串的数目

Question

LeetCode第647题

给你一个字符串，请输出该字符串里有多少个回文子字符串。如果两个子字符串的起始位置或者结束位置不同，那么即使它们的内容一样也是不同的子字符串。
例如，字符串”abc”有3个回文子字符串，分别为”a”、”b”和”c”；”aaa”有6个回文子字符串，分别为”a”、”a”、”a”、”aa”、”aa”和”aaa”。

Analysis

  • 简单解法

    以第一个字符开始查找，遍历以该字符为起始的字符子串，计算以该字符为起始的回文子串的数量。之后查找第二个字符为起始的子串，以此类推。

  • 动态规划

    分析以字符串中第i个字符结尾的子字符串中回文的数目。首先，任意一个字符本身都是一个长度为1的回文子字符串。

    其次，如果第i个字符和它前面的第i-1个字符相同。那么，它们组成一个长度为2的回文子字符串。例如：字符串”abba”中，两个相邻的”b”组成一个长度为2的回文”bb”。

    另外，如果以第i-1个字符为结尾的子字符串中有一个长度为j的回文子字符串，并且第i个字符和该回文前面一个字符（下标为i-j-1）相同，那么以第i个字符结尾的子字符串中有一个长度为j+2的回文。例如字符串”abba”中，下标为3的字符”a”（下标从0开始计数）前面有一个长度为2的回文”bb”，由于”bb”的前面的字符也是”a”，因此它们共同组成一个长度为4的回文”abba”。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def recall_str(str):
    """判断是否是回文数"""
#     if len(str) == 1:
#         return True
#     for index in range(len(str)//2):
#         if str[index] != str[-index-1]:
#             return False
    if str[:] != str[::-1]:
        return False
    return True

def count_substrings(str):
    index = 0 
    recall_num = 0
    while index < len(str):
        alpha = str[index]
        for indece in range(len(str)-index):
            if recall_str(str[index:index+indece+1]):
                print(str[index:index+indece+1])
                recall_num += 1
        index += 1
    return recall_num

print(count_substrings("ababa"))
a
aba
ababa
b
bab
a
aba
b
a
9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def count_substrings_dp(str):
    recall_num = 1 if len(str)>0 else 0
    prev_list = list()
    prev_list.append(1)
    for i in range(1, len(str)):
        cur_list = list()
        cur_list.append(1)
        if str[i] == str[i-1]:
            num_sub.append(2)
        for j in prev_list:
            if (i - j - 1) >= 0 and str[i] == str[i - j - 1]:
                cur_list.append(j+2)
        recall_num += len(cur_list)
        prev_list = cur_list
    return recall_num

print(count_substrings_dp("ababa"))
9

1
2