算法
February 7, 2019

LeetCode-Palindromic Substrings

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:

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

Example 2:

1
2
3
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. 动态规划

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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. 中心扩散

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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上看到一个大神的答案，使用纯函数实现，写得很美妙，拿过来与大家分享！

1
2
3
4
5
6
7
8
9
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返回的集合只有一个元素。

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