主題

ZeroJudge - e619: 00353 - Pesky Palindromes　解題心得

Not In My Back Yard | 2020-01-27 00:11:10 | 巴幣 0 | 人氣 319

題目連結：

題目大意：

給定一字串 s （長度不超過 80 個字元），求 s 有幾個相異且為迴文的子字串？

例如 adam 字串有 a 、 d 、 am 、 ada 四個相異的迴文子字串。因此所求為 4 。

輸出格式參見範例輸出。

範例輸入：

boy

adam

madam

tot

範例輸出：

The string 'boy' contains 3 palindromes.

The string 'adam' contains 4 palindromes.

The string 'madam' contains 5 palindromes.

The string 'tot' contains 3 palindromes.

解題思維：

因為是子字串，而非子序列（前者是連續的，後者可為非連續的序列）。所以直接窮舉所有可能的開頭、結尾字元即可得到所有的子字串。

接著篩掉重複的子字串（可以用陣列一個一個存然後判斷。也可以用映射（Map）去判斷字串是否存在）。篩完之後，直接判斷剩下的哪些是迴文，即從左到右讀跟從右到左讀是一致的。所求即是該數量。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

ETH官方钱包