在这篇文章中，我们将带领您了解[Swift]LeetCode647.回文子串|PalindromicSubstrings的全貌，同时，我们还将为您介绍有关#Leetcode#1016.BinarySt

在这篇文章中，我们将带领您了解[Swift]LeetCode647. 回文子串 | Palindromic Substrings的全貌，同时，我们还将为您介绍有关#Leetcode# 1016. Binary String With Substrings Representing 1 To N、2021-12-22：回文子串。 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。、647. Palindromic Substrings（马拉车算法）、696. Count Binary Substrings - LeetCode的知识，以帮助您更好地理解这个主题。

• [Swift]LeetCode647. 回文子串 | Palindromic Substrings
• #Leetcode# 1016. Binary String With Substrings Representing 1 To N
• 2021-12-22：回文子串。 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。
• 647. Palindromic Substrings（马拉车算法）
• 696. Count Binary Substrings - LeetCode

[Swift]LeetCode647. 回文子串 | Palindromic Substrings

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

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

输入: "abc"
输出: 3
解释: 三个回文子串: "a","c".

输入: "aaa"
输出: 6
说明: 6个回文子串: "a","aaa".

 1 class Solution {
 2     func countSubstrings(_ s: String) -> Int {
 3         var count = 0
 4         var s = Array(s)
 5         for i in 0..<s.count {
 6             if i + 1 < s.count,s[i] == s[i + 1] {
 7                 count += numpalindromes(s,i,i + 1)
 8             }
 9             count += numpalindromes(s,i)
10         }
11         return count
12     }
13 
14     func numpalindromes(_ s: [Character],_ i: Int,_ j: Int) -> Int {
15         var count = 0,i = i,j = j
16         while i >= 0,j < s.count,s[i] == s[j] {
17             i -= 1
18             j += 1
19             count += 1
20         }
21         return count
22     }
23 }

 1 class Solution {
 2     func countSubstrings(_ s: String) -> Int {
 3         var result = 0
 4         let input = Array(s)
 5         for i in 0..<input.count {
 6             checkPalindrom(i,input,&result)
 7             checkPalindrom(i,i + 1,&result)
 8         }
 9         return result
10     }
11     
12     func checkPalindrom(_ left: Int,_ right: Int,_ input: [Character],_ result: inout Int) {
13         let count = input.count
14         var i = left,j = right
15         while i >= 0,j < count {
16             if input[i] == input[j] {
17                 result += 1
18                 i -= 1
19                 j += 1
20             }else{
21                 break
22             }
23         }
24     }
25 }

 1 class Solution {
 2     func countSubstrings(_ s: String) -> Int {
 3         let arr = Array(s)        
 4         let cnt = s.count
 5         if cnt == 0 {
 6             return 0
 7         }        
 8         var result = 0
 9 
10         for center in 0..<cnt {
11             var left = center
12             var right = center
13             
14             while left >= 0 && right < cnt && arr[left] == arr[right] {
15                 result += 1
16                 left -= 1
17                 right += 1
18             }
19         }
20 
21         for center in 1..<cnt {
22             var left = center-1
23             var right = center
24             
25             while left >= 0 && right < cnt && arr[left] == arr[right] {
26                 result += 1
27                 left -= 1
28                 right += 1
29             }
30         }
31         return result
32     }    
33 }

 1 class Solution {
 2     func countSubstrings(_ s: String) -> Int {
 3         let s = Array(s)
 4         var n = s.count,ans = 0
 5         for center in 0..<2*n {
 6             var left = center / 2
 7             var right = left + center % 2
 8             while (left >= 0 && right < n && 
 9                    s[s.index(s.startIndex,offsetBy:left)] == 
10                    s[s.index(s.startIndex,offsetBy:right)]) {
11                 ans+=1
12                 left-=1
13                 right+=1
14             }
15         }
16         return ans
17     }
18 }

 1 class Solution {
 2     func countSubstrings(_ s: String) -> Int {
 3         let chars = Array(s)
 4         func extend(_ left: Int,_ right: Int) -> Int {
 5             var (left,right) = (left,right)
 6             var count = 0
 7             while left >= 0
 8                 && right < chars.count
 9                 && chars[left] == chars[right] {
10                     left -= 1
11                     right += 1
12                     count += 1
13                 }
14 
15             return count
16         }
17 
18         return chars.indices.map {
19             extend($0,$0) + extend($0,$0 + 1)
20         }
21         .reduce(0,+)
22     }
23 }

 1 class Solution {
 2     func countSubstrings(_ s: String) -> Int {
 3     guard s.count > 1 else{
 4         return 1
 5     }
 6     
 7     var manipulationStr : [Character] = []
 8     for char in Array(s){
 9         manipulationStr.append("#")
10         manipulationStr.append(char)
11     }
12     manipulationStr.append("#")
13     
14     var count : Int = 0
15     for movingIndex in 1..<manipulationStr.count - 1{
16         var leftIndex = movingIndex
17         var rightIndex = movingIndex
18         while leftIndex >= 0 && rightIndex < manipulationStr.count{
19             if manipulationStr[leftIndex] != manipulationStr[rightIndex]{
20                 break
21             }else{
22                 if manipulationStr[leftIndex] != "#"{
23                     count += 1
24                 }
25                 leftIndex -= 1
26                 rightIndex += 1
27             }
28         }
29     }
30     return count
31   }
32 }

#Leetcode# 1016. Binary String With Substrings Representing 1 To N

Input: S = "0110",N = 3 Output: true 

Input: S = "0110",N = 4 Output: false 

class Solution {
public:
    bool queryString(string S,int N) {
        int num;
        int len = S.length();
        
        for(int i = 0; i <= N; i ++) {
            string t = Binary(i);
            if(S.find(t) == -1) return false;
        }
        return true;
    }
    string Binary(int x) {
        string ans = "";
        while(x) {
            ans += x % 2 + ‘0‘;
             x /= 2;
        }
        for(int i = 0; i < ans.size() / 2; i ++) 
            swap(ans[i],ans[ans.size() - i - 1]);
        return ans;
    }
};

2021-12-22：回文子串。 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。

2021-12-22：回文子串。
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = “abc”，
输出：3，
解释：三个回文子串: “a”, “b”, “c”。
示例 2：
输入：s = “aaa”，
输出：6，
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”。
提示：
1 <= s.length <= 1000，
s 由小写英文字母组成。
力扣647。

答案2021-12-22：

马拉车算法。每个中心求个数然后求和。
时间复杂度：O(n)。
空间复杂度：O(n)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
   
    s := "moonfdd"
    ret := countSubstrings(s)
    fmt.Println(ret)
}

func countSubstrings(s string) int {
   
    if len(s) == 0 {
   
        return 0
    }
    dp := getManacherDP(s)
    ans := 0
    for i := 0; i < len(dp); i++ {
   
        ans += dp[i] >> 1
    }
    return ans
}

func getManacherDP(s string) []int {
   
    str := manacherString(s)
    pArr := make([]int, len(str))
    C := -1
    R := -1
    for i := 0; i < len(str); i++ {
   
        if R > i {
   
            pArr[i] = getMin(pArr[2*C-i], R-i)
        } else {
   
            pArr[i] = 1
        }
        for i+pArr[i] < len(str) && i-pArr[i] > -1 {
   
            if str[i+pArr[i]] == str[i-pArr[i]] {
   
                pArr[i]++
            } else {
   
                break
            }
        }
        if i+pArr[i] > R {
   
            R = i + pArr[i]
            C = i
        }
    }
    return pArr
}

func manacherString(str string) []byte {
   
    charArr := []byte(str)
    res := make([]byte, len(str)*2+1)
    index := 0
    for i := 0; i != len(res); i++ {
   
        if i&1 == 0 {
   
            res[i] = ''#''
        } else {
   
            res[i] = charArr[index]
            index++
        }
    }
    return res
}

func getMin(a, b int) int {
   
    if a < b {
   
        return a
    } else {
   
        return b
    }
}

执行结果如下：

左神java代码

647. Palindromic Substrings（马拉车算法）

##问题 求一个字符串有多少个回文子串

Input: "abc" Output: 3 Input: "aaa" Output: 6

##思路和代码（1）——朴素做法 用dp的基本思想“子问题求解”，但是因为没有重叠子问题，没必要用dp数组或者矩阵来存储中间结果。 直接遍历每个字符，然后以该字符为中心向两边扩张来判断是否回文串，是的话就总数加1。 这时要考虑两种情况，一种是以单字符为中心来扩张即aba这种，另一种是以双字符为中心来扩张即abba。 对于每个字符s[i]要遍历两次扩张，一次以s[i]为中心来扩张，一次以s[i]和s[i+1]为中心来扩张。因此需要遍历2n次（n为字符串长度）。又考虑到最后一个字符s[n-1]后面已经没有字符了，不需要考虑以两个字符为中心的情况，所以实际是遍历2n-1次。 可以用两个指针left和right，单字符为中心的扩张时left和right都初始指向s[i]，双字符为中心的扩张时left指向s[i]，right指向s[i+1]。

时间复杂度O(n^2)，空间复杂度O(1)

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        res = 0
        for i in range(2*n-1):
            left = i/2
            right = left + i%2
            while(left >= 0 and right < n and s[left]==s[right] ):
                res += 1
                left -= 1
                right += 1
        return res

##思路和代码（2）——Manacher算法 使用马拉车算法，算法根据回文串的对称特点利用之前的信息计算，可以在线性时间内找出所有回文串。

“原字符串”转为“#字符串” 前面说了回文串分为单字符中心和双字符中心，为了可以统一按单字符中心处理。首先在原字符中插入字符''#''，例如aaa经过插入处理后得到"#a#a#a#"，这样遍历到第一个a时其实是以a为单字符中心，遍历到第二个#时就是以aa为双字符中心。第一个#和最后一个#的意义在于补全第一个字符和最后一个字符的“回文串身份”，因为单个字符也算回文串。

镜像计算 我们用p[i]表示以i为中心的回文串半径，p[i]初始化为0。正常情况，我们根据扩张的方法来判断半径是否增加。 特殊情况，如果字符s[i]处于某个已知的“以id为中心，以mx为右边界”的回文串中（此时mx > i），我们称这个回文串为id回文串，此时可以利用id为中心对称过去的镜像索引来简化计算，我们称镜像索引为j。然后有两种情况。

如果p[j]<mx-i，说明i的半径没有超出mx的边界而且等于j的半径，此时p[i]=[j]=p[2*id-1]，这个p[i]值是确定的。

如果p[j]>=mx-i，说明i的半径至少扩张到了mx，mx之后的部分要继续扩张。此时p[i]值不是确定的，但是我们让p[i]=mx-i，因为半径为mx-i是至少的，至于半径是否继续增加取决于mx后面的部分，我们在扩张步骤计算。

简化以上两种情况可以得到：如果mx > i，那么p[i] = min(p[2*id-1], mx-i)

扩张 根据上面的说明，只有在mx >i 以及 p[j] < mx-i的情况下可以通过镜像计算来直接获得半径，其它情况还是要继续扩张。扩张的计算很简单，在当前半径的基础上扩张，判断s[i+p[i]+1]和s[i-p[i]-1]是否相等，相等则半径p[i]加1。

更新id回文串 遍历过程中，如果发现有右边界更大的回文串，则覆盖这个回文串。

“#字符串”的回文个数->“原字符串”的回文个数： 上面计算的半径p[i]会因为#的插入而增多，所以要根据“#字符串”的半径计算一下，得到“原字符串”的半径。我们把所有半径加起来就可以计算出回文字串的数量。

举个双字符为中心的例子，#a#a#，中间#的半径为a#，要转为半径a，2要转为1，直接除以2就得到了。

举个单字符为中心的例子，#a#a#b#a#a#，b的半径#a#a#，要转为半径aa，5要转为2，但是考虑b本身也是一个回文串，实际上是5要转为3，这个时候需要加1之后除以2（这里跟半径的定义有关，我这里的定义中b这个单字符的半径为0。如果定义的b的半径为1，这里的计算就不是加1而是减1了）。

综合来看，直接加1除以2就可以了，因为/会向下取整。

时间复杂度O(n)，空间复杂度O(1)

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        s = ''#'' + ''#''.join(s) + ''#''
        n = len(s)
        p = [0]*n
        id = mx = res = 0
        for i in range(1,n-1):
            if(mx > i):
                p[i] = min(mx-i, p[2*id-i])
            while i+p[i]+1 < n and i-p[i]-1 >=0 and s[i+p[i]+1] == s[i-p[i]-1]:
                p[i] += 1
            if(i + p[i] > mx):
                id = i
                mx = i + p[i]
            res += (p[i]+1)/2
        return res

696. Count Binary Substrings - LeetCode

Question

696. Count Binary Substrings

Example1

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1''s and 0''s: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0''s (and 1''s) are not grouped together.

Example2

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1''s and 0''s.

Solution

题目大意:

给一个只有01组成的字符串,求子串数,子串必须满足

1. 0和1出现次数一样
2. 保证0连续1连续

思路:

参考下面参考链接的思路:

上一个连续子串长度记为preRunLength,当前连续子串长度记为curRunLength,res记为满足条件的子串数

Java实现:

public int countBinarySubstrings(String s) {
    int preRunLength = 0, curRunLength = 1, res = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) { // 当前字符与上一字符相同,表示当前连续子串未断
            curRunLength++; // 当前连续子串长度加1
        } else { // 当前字符与上一字符不同,表示当前连续子串结束
            preRunLength = curRunLength; // 当前连续子串长度变为上一个连续子串长度
            curRunLength = 1; // 当前连续子串长度为1
        }
        if (preRunLength >= curRunLength) res++; // 当前连续子串长度小于上一个连续子串长度就满足要求
    }
    return res;
}

Ref

Java-O(n)-Time-O(1)-Space

关于[Swift]LeetCode647. 回文子串 | Palindromic Substrings的介绍现已完结，谢谢您的耐心阅读，如果想了解更多关于#Leetcode# 1016. Binary String With Substrings Representing 1 To N、2021-12-22：回文子串。 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。、647. Palindromic Substrings（马拉车算法）、696. Count Binary Substrings - LeetCode的相关知识，请在本站寻找。