腾讯&leetcode647：回文子串 #107

Activity

1. sisterAn

   added

   腾讯

   LeetCode

   on Sep 14, 2020
2. marlboroKay commented on Sep 14, 2020

   

   marlboroKay

   on Sep 14, 2020

   More actions

   var countSubstrings = function(s) {
     let len = s.length;
     let res = 0;
     for(let i = 0; i < len; i++){
       let str = '';
       let revStr = '';
       for(let j = i; j < len; j++){
         str += s[j];
         revStr = s[j] + revStr;
         if(str === revStr) res++;
       }
     }
     return res;
   };
   
   //中心扩展法
   var countSubstrings = function(s) {
     let len = s.length;
     let res = 0;
     for(let i = 0; i < 2*len - 1; i++){
       let l = i/2, r = i/2 + i%2;
       while(l >= 0 && r < len && s.charAt(l) == s.charAt(r)){
         l--;
         r++;
         res++;
       }
     }
     return res;
   }
3. sisterAn commented on Sep 14, 2020

   

   sisterAn

   on Sep 14, 2020

   OwnerAuthor

   More actions

   解法一：暴力法

   let countSubstrings = function(s) {
     let count = 0
     for (let i = 0; i < s.length; i++) {
       for (let j = i; j < s.length; j++) {
         if (isPalindrome(s.substring(i, j + 1))) {
           count++
         }
       }
     }
     return count
   }
   
   let isPalindrome = function(s) {
     let i = 0, j = s.length - 1
     while (i < j) {
       if (s[i] != s[j]) return false
       i++
       j--
     }
     return true
   }

   复杂度分析：

   • 时间复杂度：O(n³)
   • 空间复杂度：O(1)

   解法二：动态规划

   一个字符串是回文串，它的首尾字符相同，且剩余子串也是一个回文串。其中，剩余子串是否为回文串，就是规模小一点的子问题，它的结果影响大问题的结果。

   我们怎么去描述子问题呢？

   显然，一个子串由两端的 i 、j 指针确定，就是描述子问题的变量，子串 s[i...j] （ dp[i][j] ） 是否是回文串，就是子问题。

   我们用二维数组记录计算过的子问题的结果，从base case出发，像填表一样递推出每个子问题的解。

       j
       a  a  b  a
   i a ✅
     a    ✅  
     b       ✅
     a          ✅

   注意： i<=j ，只需用半张表，竖向扫描

   所以：

   i === j： dp[i][j]=true
   j - i == 1 && s[i] == s[j]： dp[i][j] = true
   j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]： dp[i][j] = true

   即：

   s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]): dp[i][j]=true

   否则为 false

   代码实现：

   let countSubstrings = function(s) {
     const len = s.length
     let count = 0
     const dp = new Array(len)
   
     for (let i = 0; i < len; i++) {
       dp[i] = new Array(len).fill(false)
     }
     for (let j = 0; j < len; j++) {
       for (let i = 0; i <= j; i++) {
         if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
           dp[i][j] = true
           count++
         } else {
           dp[i][j] = false
         }
       }
     }
     return count
   }

   代码实现（优化）：

   把上图的表格竖向一列看作一维数组，还是竖向扫描，此时仅仅需要将 dp 定义为一维数组即可

   let countSubstrings = function(s) {
     const len = s.length
     let count = 0
     const dp = new Array(len)
   
     for (let j = 0; j < len; j++) {
       for (let i = 0; i <= j; i++) {
         if (s[i] === s[j] && (j - i <= 1 || dp[i + 1])) {
           dp[i] = true
           count++
         } else {
           dp[i] = false
         }
       }
     }
     return count;
   }

   复杂度分析：

   • 时间复杂度：O(n²)
   • 空间复杂度：O(n)

   leetcode

   👍React with 👍1Reacted by 行书子
4. sisterAn

   added

   阿里

   on Sep 18, 2020
5. doctorFei commented on Oct 11, 2020

   

   doctorFei

   on Oct 11, 2020

   More actions

   //中心扩展法
   /**
    * @param {string} s
    * @return {number}
    */
   var countSubstrings = function(s) {
       let nums = s.length;
       if(s.length<2){
           return nums
       }
       function lookByCenter(left,right){
           while (left>=0&&right<s.length&&s[left]===s[right]){
               nums++
               left--
               right++
           }
       }
   
       for (let i = 0;i<s.length;i++){
           lookByCenter(i-1,i+1)
           lookByCenter(i,i+1)
       }
   
       return nums
   };
6. TonyZhang1993 commented on Feb 28, 2024

   

   TonyZhang1993

   on Feb 28, 2024

   Last edited by TonyZhang1993

   More actions

   改写自 最长回文子串；

   var countSubstrings = function(s) {
     let res = 0
   
     for (let i=0; i<s.length; i++) {
       // 以 s[i] 为中心的最长回文子串 - 奇数情况
       let s1 = palindrome(s, i, i)
       // 以 s[i] 和 s[i+1] 为中心的最长回文子串 - 偶数情况
       let s2 = palindrome(s, i, i+1)
   
       res += s1
       res += s2
   
     }
   
     return res
   
     // 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
     function palindrome(s, l, r) {
       let res = 0
       //  边界情况
       while (l>=0 && r<s.length && s[l] === s[r]) {
         //  向两边展开
         l--
         r++
         res++
       }
   
       // return s.slice(l+1, r)
       return res
     }
   }
   
   //  时间复杂度：O(n2)
   //  空间复杂度：O(1)