leetcode696、計數二進制子串

題目

給定一個字元串，你需要反轉字元串中每個單詞的字元順序，同時仍保留白格和單詞的初始順序。

示例 1：

輸入: “00110011”

輸出: 6

解釋: 有6個子串具有相同數量的連續1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

請注意，一些重複出現的子串要計算它們出現的次數。

另外，“00110011”不是有效的子串，因為所有的0（和1）沒有組合在一起。

示例2：

輸入: “10101”

輸出: 4

解釋: 有4個子串：“10”，“01”，“10”，“01”，它們具有相同數量的連續1和0。

方法1：

1. 以00110011為例，從第一位開始，逐漸向後移，找到第一個含0的子串或含1的子串，然後拼接對應相反的子串，如先找到00，然後取反得11，拼接成0011，然後看看00110011是否是從0011開始的，是的話則表示找到這個子串
2. 然後繼續從第二位開始，找到0，然後取反為1，拼接成01，看看從第二位開始看看0110011是否是以01開頭，是的話就找到子串，以此類推，代碼如下：

const countBinarySubstrings = function(s) {
    let count = 0
    const match = str => {
        let s1 = str.match(/(0+|1+)/)[0]
        let s2 = (s1[0] ^ 1).toString().repeat(s1.length) 
        let s3 = s1 + s2
        if (s3 === str.slice(0, s1.length * 2)) {
            return true
        } else {
            return false
        }
    }
    for (var i = 0; i < s.length - 1; i++) {
        var sub = match(s.slice(i))
        if (sub) {
            count++
        }
    }
    return count
};
           

缺點：

1. 重複計算太多，如000111是一個合格的子串，那麼表示0011也是，01也是，其實周遊步長不需要為1
2. 使用太多API，性能低下

方法2：解決重複計算

1. 以000111000為例，确認000111為合格子串之後，增加合格子串數目為 6 / 2 = 3，周遊下标直接跳到1處，從111000開始

const countBinarySubstrings = function(s) {
    let count = 0
    const match = str => {
        let s1 = str.match(/(0+|1+)/)[0]
        let s2 = (s1[0] ^ 1).toString().repeat(s1.length) 
        let s3 = s1 + s2
        if (s3 === str.slice(0, s1.length * 2)) {
            return s3
        } else {
            return ''
        }
    }
    for (let i = 0; i < s.length - 1;) {
        let goodStr = match(s.slice(i))
        if (goodStr.length > 0) {
            count += goodStr.length / 2
            i += goodStr.length / 2
        } else {
            i++
        }
    }
    return count
};
           

缺點：

1. 使用太多API，性能低下

方法3：解決用太多API方法

const countBinarySubstrings = function(s) {
    if (s.length <= 1) return 0
    let preRun = 0
    let curRun = 1
    let count = 0
    for (let i = 1; i < s.length; i++) { 
        if (s[i - 1] === s[i]) {
            curRun++
        } else { 
            preRun = curRun
            curRun = 1 
        }
        if (preRun >= curRun) {
            count++
        }
    }
    return count
};
           

性能最優