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] 문자가 나타나지 않습니다.

"스캔된 문자가 이동할 수 있는 가장 먼 위치"를 유지하십시오. 이 위치로 스캔하면 나중에 잘린 문자가 나타나지 않습니다. 시작 포인터를 업데이트하고 다음 컷을 준비하세요.

일부 변수

maxPos 각 문자에 해당하는 가장 먼 위치를 기록하는 지도입니다. start는 절단의 시작 위치입니다. scanningCharMaxPos 스캔된 문자가 이동할 수 있는 가장 먼 위치입니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!