LeetCode-Palindromic Substrings

た入场券 2022-04-23 10:22 127阅读 0赞

### 文章目录 ###

*  LeetCode-Palindromic Substrings
 *   *  题目描述
     *  思路分析
     *  C++实现
     *  Scala实现

# LeetCode-Palindromic Substrings #

## 题目描述 ##

这是第647道题目：[Palindromic Substrings][]

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

**Example 1:**

Input: "abc"
    Output: 3
    Explanation: Three palindromic strings: "a", "b", "c".

**Example 2:**

Input: "aaa"
    Output: 6
    Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

题目要求是需要计算出给定字符串中所有回文子串的个数（单个字符也算一个回文子串，不同索引位置的相同内容的回文子串也算不同的回文）

## 思路分析 ##

有两种思路：一种是采用动态规划的方法；另一种是采用中心扩散的方法。

1.  动态规划
    
    如果用`dp[i][j]`表示从第`i`个字符到第`j`个字符是不是回文子串，`s`表示给定字符串，则有
    
    `dp[i][j]`= (`s[i]` == `s[j]`) && (`i` \- `j` < 2) （这里表示的是子串是一个字符，两个字符的情形）
    
    `dp[i][j]`= (`s[i]` == `s[j]`) && (`dp[i + 1][j -1]` ) （这里表示的是除了前面两种情形之外的情形）
    
    注：三个字符串的情形既可以归类到第一种情况（如果归类到第一种情况，则条件需要变为`i` \- `j` < 3），也可以归类到第二种情形
2.  中心扩散
    
    扩散法假定一个中心，然后采用左右两个指针同时向两边走来判断是不是回文。
    
    注：中心扩散法需要区分回文子串中的字符个数是奇数和偶数两种情况。

## C++实现 ##

1.  动态规划
    
        class Solution {
        public:
            int countSubstrings(string s) {
                const int N = static_cast<int>(s.size());   // 如果不强转就会超时，好奇怪
                int count = 0;
                // 下面这一行换成原生数组也是可以的int dp[N][N]
                vector<vector<bool>> dp(N, vector<bool>(N));
                // 从后面遍历是为了让求dp[i][j]的时候dp[i + 1][j - 1]是已经计算过的
                for (auto i = N - 1; i >= 0; --i) {
                    for (auto j = i; j < N; ++j) {
                        // (j - i < 2)包含了两种情况，使得dp[i + 1][j - 1]可以包含剩下的所有情况
                        dp[i][j] = (s[i] == s[j]) && ((j - i < 2) || dp[i + 1][j - 1]);
                        if (dp[i][j]) count++;
                    }
                }
        
                return count;
            }
        };
    
    在使用C++实现的时候，我发现一些有意思的现象：
    
    1.  在第四行`s.size()`的返回类型本来是`size_t`，但是如果直接使用`size_t`的话，运行直接超时。我强制转换为`int`以后就可以通过测试。有童鞋能帮我解答一下疑惑吗？?
    2.  用于存储`dp`的使用动态数组`vector`是一般都会想到的，但是我看到一些提交中也有直接使用C++原生数组的。我就奇怪了，C++原生数组的话需要使用`new`操作符去动态申请，为什么直接使用也可以通过编译呢？我后来查了一些资料，原来C99标准中支持了原生动态数组（标准中称之为变成数组variable length array）。但是C++标准中这个特性是可选的，就是说可能有的编译器支持这样写，而有的编译器不行。不过，原生数组相对`vector`容器，效率会更高一些。如果你的编译器支持，大胆地使用吧！
2.  中心扩散
    
        class Solution {
        private:
            int count = 0;
            void extendPalindrome(const string& s, int left, int right) {
                while ((left >= 0) && (right < s.size()) && (s[left] == s[right])) {
                    --left;
                    ++right;
                    ++count;
                }
            }
        
        public:
            int countSubstrings(string s) {
                for (int i = 0; i < s.size(); ++i) {
                    extendPalindrome(s, i, i);      // 对于奇数个字符的回文
                    extendPalindrome(s, i, i + 1);  // 对于偶数个字符的回文
                }
                return count;
            }
        };

## Scala实现 ##

Scala的实现是在LeetCode上看到一个大神的答案，使用纯函数实现，写得很美妙，拿过来与大家分享！

object Solution {
        def countSubstrings(s: String): Int = {
            (for {
                i <- 0 until s.length
                j <- List(i, i + 1)
                _ <- (i to 0 by -1).zip(j until s.length).takeWhile(p => s(p._1) == s(p._2))
            } yield true).length
        }
    }

这也是采用中心扩散法实现的。

`for`循环中的`i`从左到右依次遍历给定字符串，`j`控制的是奇数个数的子串情况和偶数个数的子串情况，`for`循环中的第三个匿名变量其实相当于一个条件判断。整个`for`循环返回一个`vector`（里面都是`true`），最后统计这个`vector`个中包含元素的个数即可。

这里重点说一下`for`循环中的第三个匿名循环控制语句。`(i to 0 by -1).zip(j until s.length)`生成一个从中间向两边扩散的`List`（其实是`List`的子类`::`非空链表），这个`List`中的每个元素是一个`Tuple2`包含的是左指针`i`和右指针`j`。`takeWhile`方法是起到一个过滤作用，将左指针和右指针指向的值相等的这`Tuple2`返回（其实返回类型是`::`,只是里面只有一个元素）。如果左指针和右指针指向的值不相等，则返回`Nil（一个空的List）`。如果返回的是`Nil`的话，则不会生成一个`true`。这样子，其实第三个循环控制语句起到的是判断的作用。

注：

1.  Scala中的`Vector`类似于Java中的`ArrayList`，而Scala中的`List`类似于Java中的`LinkedList`
2.  Scala中的`List`有两个特殊的子类：`::`表示非空的`List`，`Nil`表示空的`List`
3.  函数`filter`和`takeWhile`都可以起到过滤的作用，`filter`会过滤出给定集合中所有满足条件的元素，而`takeWhile`只会返回第一个满足条件的元素。但是两者返回的都是集合，即使`takeWhile`返回的集合只有一个元素。

感觉函数式编程是挺好玩的，只是现在水平有限，还玩不起来！继续加油！

[Palindromic Substrings]: https://leetcode.com/problems/palindromic-substrings/