PHPで文字間隔を分割する方法

文字列 S は小文字で構成されます。この文字列をできるだけ多くのセグメントに分割する必要があります。同じ文字はいずれかのセグメントにのみ表示されます。各文字列フラグメントの長さを表すリストを返します。今回は文字間隔の分割方法を紹介します。

文字間隔を分割します

文字列 S は小文字で構成されます。この文字列をできるだけ多くのセグメントに分割する必要があります。同じ文字はいずれかのセグメントにのみ表示されます。各文字列フラグメントの長さを表すリストを返します。

例 1:

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

ヒント:

S の長さは [1, 500] の間です。 S には小文字の「a」から「z」のみが含まれます。

問題解決のアイデア 1

カットしたい場合は、最初と最後の 2 つのポインターが必要です。終了ポインターが決定したら、次のことができます。次の切断の開始ポインタを決定します。文字列を走査し、スキャンした部分のすべての文字がスキャン範囲内にのみ表示される場合は、それを切り取ることができます。下の図でスキャンされた緑色の文字は、8 を超える最も遠い位置に対応していません。8 でカットすると、[0:8] の文字は他の場所に表示されなくなります。

「スキャンした文字が到達できる最も遠い位置」を維持します。この位置までスキャンするとカットされます。カットされた文字は後で表示されません。開始ポインタを更新し、次のカットの準備をします。

いくつかの変数

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 中国語 Web サイトの他の関連記事を参照してください。