PHP怎么實現劃分字母區間

本篇內容介紹了“PHP怎么實現劃分字母區間”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

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

劃分字母區間

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

示例 1：

輸入：S = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：劃分結果為 "ababcbaca", "defegde", "hijhklij"。
每個字母最多出現在一個片段中。
像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數較少。

提示：

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

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/partition-labels 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題思路 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怎么實現劃分字母區間”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！