PHP如何分割字母區間

字串S由小寫字母組成。我們要把這個字串分成盡可能多的片段，同一個字母只會出現在其中的一個片段。傳回一個表示每個字串片段的長度的清單。今天我們就來介紹劃分字母區間的方法。

分割字母區間

#字串 S 由小寫字母組成。我們要把這個字串分成盡可能多的片段，同一個字母只會出現在其中的一個片段。傳回一個表示每個字串片段的長度的清單。

範例 1：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

#S的長度在[1, 500]之間。 S只包含小寫字母 ‘a’ 到 ‘z’ 。

解題思路 1

想切割，要有首尾兩個指針，確定了結尾指針，就能確定下一個切割的開始指針。遍歷字串，如果已掃描部分的所有字符，都只出現在已掃描的範圍內，即可做切割。下圖已掃描的綠色字符，對應的最遠位置，都不超過 8，在 8 這切一刀，[0:8] 的字符都不會出現在別處。

maintain「已掃描的字元能去到的最遠位置」，掃到這個位置就切割，切出的字元不會在之後出現。更新開始指針，準備下一次切割。

一些變數

maxPos 一個Map，記錄每個字母對應的最遠位置。 start 做切割的開始位置。 scannedCharMaxPos 已掃描的字元能去到的最遠位置。

class Solution {
    /** 
    * @param String $S 
    * @return Integer[] 
    */
    function partitionLabels($S) {
        $maxPos = [];
        $length = strlen($S);
        for ($i = 0; $i < $length; $i++) { // 存放字母与它的最远位置
            $maxPos[$S[$i]] = $i;
        }
        $res = [];
        $start = 0;                        // 待切割的起始位置
        $scannedCharMaxPos = 0;            // 已扫描的字符中最远的位置
        for ($i = 0; $i < $length; $i++) {
            $curCharMaxPos = $maxPos[$S[$i]]; // 当前扫描的字符的最远位置
            $scannedCharMaxPos = max($scannedCharMaxPos, $curCharMaxPos); // 更新「已扫描的字符中最远的位置」
            if ($i == $scannedCharMaxPos) { // 正好扫描到「已扫描的字符的最远位置」，到达切割点
                $res[] = $i - $start + 1;
                $start = $i + 1;              // 更新，下一个待切割的字符串的起始位置
            }
        }
        return $res;
    }}

推薦學習：php影片教學

#

以上是PHP如何分割字母區間的詳細內容。更多資訊請關注PHP中文網其他相關文章！