雙指針算法在實際開發中的具體應用之代碼Review文章字符串的片段分割详情 - 雙指針,leetcode,算法,javascript 水冗水孚日志

本文是筆者在實際中具體遇到的場景，從中提取具體的核心的部分，使用前後指針進行性能優化的具體案例

開發需求場景

前段時間，筆者在做代碼Review的時候，發現了一個需求的前端實現方案不太優雅
組員選擇使用了循環加切割的方案去處理這個字符串
筆者最終將其改為，使用快慢指針的方式，讓其變得更加優雅，性能更佳

需求描述

後端有一個字段返回一篇中文文章的具體內容
比如有一個artical文章字段的值是一個長長的字符串
需求抽象成：let artical = '白日依山盡，黃河入海流。欲窮千里目，更上一層樓。'
前端展示的時候，需要一行一行展示（標點符號分隔，一句話就是一行）
比如上述的artical的值，最終會展示成

<p>白日依山盡</p>
<p>黃河入海流</p>
<p>欲窮千里目</p>
<p>更上一層樓</p>

循環加切割的方案

他的實現思路是：

先第一遍遍歷，把原來的字符串“拷貝”一份，如果遇到了標點符號，統一使用橫槓替換，最後再以橫槓為標識，將字符串切割成數組，從而完成需求

實際上的標點符號，除了逗號、句號之外，還有問號，感嘆號，省略號等，這裏是為了更便於理解，抽象成為簡單模型

代碼

let artical = '白日依山盡，黃河入海流。欲窮千里目，更上一層樓。'

function toArr(str) {
    let s = ['，', '。']
    let ns = ''
    for (let i = 0; i < str.length - 1; i++) {
        if (s.includes(str[i])) {
            ns = ns + '-'
        } else {
            ns = ns + str[i]
        }
    }
    return ns.split('-')
}

const result = toArr(artical)
console.log('result', result)

點評

首先，時間複雜度高，每次拼接都會複製整個已有字符串，字符串越長，複製的成本越高，累積起來甚至達到平方級的耗時。而artical字段的值，也不小，所以這種拼接方式效率不太高
然後，有依賴特殊字符風險，若原字符串中本身包含 -，那麼split('-') 則是會錯誤分割，尷尬了

快慢雙指針方案

實現思路是

定義兩個指針l和r，初始都在起點索引為0的地方
使用while循環，讓第一個指針r先往右跑
當r遇到標點符號的時候，截取l到r的區間的字符串存到數組裏面
而後，再讓l趕上r，r再往右跑，直到跑到頭，跑完整個article字符串
有點像，張三和李四拿着捲尺丈量操場的長度
李四原地不動，張三拉着捲尺到頭，記錄一段距離
李四再跑到張三的位置，張三再往前跑同時把卷尺拉到頭
如下動畫：

代碼

let artical = '白日依山盡，黃河入海流。欲窮千里目，更上一層樓。'

function toArr(str) {
    let s = ['，', '。']
    let arr = []
    let l = 0
    let r = 0
    while (r <= str.length - 1) {
        if (s.includes(str[r])) {
            let range = str.slice(l, r)
            arr.push(range)
            r = r + 1
            l = r
        } else {
            r = r + 1
        }
    }
    return arr
}
const result = toArr(artical)
console.log('result', result)

最終使用Set集合去判斷是否是標點符號，即

function toArr(str) {
    let s = new Set(['，', '。'])
    let arr = []
    let l = 0
    let r = 0
    while (r <= str.length - 1) {
        if (s.has(str[r])) {
            let range = str.slice(l, r)
            arr.push(range)
            r = r + 1
            l = r
        } else {
            r = r + 1
        }
    }
    return arr
}