LeetCode 帮助，3 个字母回文题 - 中

Question

leetocde上有这样的问题： 给定一个字符串 s，返回作为 s 子序列的长度为 3 的唯一回文数。

注意，即使有多种方式获得同一个子序列，仍然只计算一次。

回文是向前和向后读取相同的字符串。

字符串的子序列是在原字符串中删除一些字符（可以没有）而生成的新字符串，而不改变其余字符的相对顺序。

解决方法：查找。第一次和最后一次出现的字母，计算其间不同的唯一字母，不要忘记同一字母的帐户，例如“aaa”

我写了这个解决方案：

func countPalindromicSubsequence(s string) int {
    p := make(map[rune][2]int)
    o := make(map[rune]int)
    total := 0
    for i, v := range s {
        o[v]++
        _, ok := p[v]
        if !ok {
            /// this is the first time we record this number
            s :=[2]int{i,0}
            p[v]  = s
            
        }else {
            s := p[v] 
            s[1] = i
            p[v]  = s
        }
    }

    for k,v := range p {
        if v[1] == 0 {
            continue
        }
        if o[k] >= 3 {
            total++
        }
        //// count palindromes in between
        for l, value := range p {
            if l != k && ((value[0] > v[0] && value[0] < v[1]) || (value[1] > v[0] && value[1] < v[1])){
                total ++
            }
        }
        
    }
    
   return total
}

它在“tlpjzdmtwderpkpmgoyrcxttiheassztncqvnfjeyxxp”上失败 我正在调试它，但没有运气 有人可以帮忙吗？

Answer 1

郑重声明，这是 LeetCode 1930. 唯一长度 3 回文子序列 问题。

要解决此问题，请注意回文子序列类似于

x...x

，其中

...

表示任意一个或多个字母。上述字符串中长度为 3 的回文子序列的数量由

j - i - 1

给出，其中

i

是第一个

x

的索引，

j

是最后一个

。

因此，我们首先迭代字符串并收集哈希映射中每个字母的第一个和最后一个索引。然后我们再迭代一次，对于每一对，计算这些索引之间唯一字母的数量。

以下是一个 Python 解决方案，我相信您可以轻松转换为 Go。

def countPalindromicSubsequence(s: str) -> int:
    indices: dict[int, list[int]] = {}
    for i, c in enumerate(s):
        x = indices.get(c, [i, i])
        x[1] = i
        indices[c] = x

    return sum(len(set(s[start + 1: end])) for start, end in indices.values() if start != end)