문자열에 공백 추가

2109. 문자열에 공백 추가

난이도:중

주제: 배열, 두 포인터, 문자열, 시뮬레이션

인덱스가 0인 문자열 s와 공백이 추가될 원래 문자열의 인덱스를 설명하는 인덱스가 0인 정수 배열 공백이 제공됩니다. 각 공백은 해당 인덱스의 문자 앞에 삽입되어야 합니다.

• 예를 들어 s = "EnjoyYourCoffee"이고 공백 = [5, 9]인 경우 각각 인덱스 5와 9에 있는 'Y'와 'C' 앞에 공백을 배치합니다. 그리하여 "Enjoy Your Coffee"를 획득하게 되었습니다.

공백을 추가한 후수정된 문자열을 반환합니다.

예 1:

• 입력: s = "LeetcodeHelpsMeLearn", 공백 = [8,13,15]
• 출력: "Leetcode는 학습에 도움이 됩니다."
• 설명: 인덱스 8, 13, 15는 "LeetcodeHelpsMeLearn"의 밑줄 친 문자에 해당합니다.
  • 그런 다음 해당 문자 앞에 공백을 넣습니다.

예 2:

• 입력: s = "icodeinpython", 공백 = [1,5,7,9]
• 출력: "i code in py thon"
• 설명: 인덱스 1, 5, 7, 9는 "icodeinpython"의 밑줄 친 문자에 해당합니다.
  • 그런 다음 해당 문자 앞에 공백을 넣습니다.

예 3:

• 입력: s = "간격", 공백 = [0,1,2,3,4,5,6]
• 출력: "s p a c i ng"
• 설명: 문자열의 첫 문자 앞에 공백을 넣을 수도 있습니다.

제약조건:

• 1 5
• s는 영문 소문자와 대문자로만 구성됩니다.
• 1 5
• 0
• 공간의 모든 가치는 엄청나게 증가합니다.

힌트:

1. 수정된 문자열로 처음에는 비어 있는 새 문자열을 만듭니다. 원래 문자열을 반복하고 원래 문자열의 각 문자를 새 문자열에 추가합니다. 그러나 앞에 공백이 필요한 문자에 도달할 때마다 문자를 추가하기 전에 공백을 추가하십시오.
2. 공간 위치에 대한 색인 배열이 정렬되어 있으므로 포인터를 사용하여 공간을 배치할 다음 색인을 추적하세요. 공백이 추가된 후에만 포인터를 증가시키세요.
3. 추가 작업이 O(1)에서 수행될 수 있는지 확인하세요.

해결책:

두 개의 포인터를 사용하여 효율적인 접근 방식을 사용할 수 있습니다. PHP 5.6의 구현은 다음과 같습니다.

솔루션 설명:

1. 포인터 spaceIndex를 사용하여 공백 배열의 현재 위치를 추적하세요.
2. 루프를 사용하여 문자열 s를 반복합니다.
3. 문자열의 현재 인덱스가 공백 배열의 현재 값과 일치하는지 확인하세요. 그렇다면 결과에 공백을 추가하고 spaceIndex 포인터를 앞으로 이동하세요.
4. 현재 문자열 문자를 결과에 추가합니다.
5. 최종 결과를 단일 문자열로 반환합니다.

이 접근 방식을 사용하면 공백 배열의 정렬된 순서를 활용하여 입력을 효율적으로 처리할 수 있습니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2109. 문자열에 공백 추가

<?php /**
 * @param String $s
 * @param Integer[] $spaces
 * @return String
 */
function addSpaces($s, $spaces) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$s1 = "LeetcodeHelpsMeLearn";
$spaces1 = [8, 13, 15];
echo addSpaces($s1, $spaces1) . "\n"; // Output: "Leetcode Helps Me Learn"

// Example 2
$s2 = "icodeinpython";
$spaces2 = [1, 5, 7, 9];
echo addSpaces($s2, $spaces2) . "\n"; // Output: "i code in py thon"

// Example 3
$s3 = "spacing";
$spaces3 = [0, 1, 2, 3, 4, 5, 6];
echo addSpaces($s3, $spaces3) . "\n"; // Output: " s p a c i n g"
?>

설명:

1. 효율적인 추가: . PHP의 연산자는 문자열을 효율적으로 추가하는 데 사용됩니다.
2. 두 개의 포인터: spaceIndex 포인터는 공백 배열을 한 번만 처리하도록 보장합니다.
3. 시간 복잡성:
   • 문자열을 반복하려면 O(n)이 필요합니다. 여기서 n은 문자열의 길이입니다.
   • 공백 배열 포인터를 확인하려면 O(m)이 필요합니다. 여기서 m은 공백 배열의 길이입니다.
   • 결합: O(n m), 이는 제약 조건을 고려할 때 최적입니다.

이 솔루션은 제약 조건을 준수하며 대규모 입력에도 효율적입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 문자열에 공백 추가의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!