leetcode_680

找出字符串的所有回文子串

思路：一个字符串为单个字符则肯定是回文串，两个字符则需要相等，三个字符则两侧相等且中间的部分为回文串，那么动态规划解法如下

var countSubstrings = function(s) {
    let len = s.length
    let dp=[]
    let result = 0
    let list = s.split('')
    for(let i = 0; i<len; i++) {
        dp[i]=Array(len).fill(false)
        for(let j=0; j<=i; j++) {
            if(list[i]===list[j] && (i-j<2 || dp[i-1][j+1])) {
                dp[i][j]=true
                result++
            } 
        }
    }
    return result
};

删除一个字符后是否为回文串

var validPalindrome = function(s) {
   let left =0
   let right = s.length-1
   let list = s.split('')
   while(right>left) {
       if(list[left] === list[right]){
           left++
           right--
       } else {
           let afterLeft = [...list]
           afterLeft.splice(left,1)
           let afterRight = [...list]
           afterRight.splice(right,1)
           if(afterLeft.toString() === afterLeft.reverse().toString() || afterRight.toString() === afterRight.reverse().toString()) {
               return true
           } else {
               return false
           }
       }
   }
   return true
};