조각을 움직여서 끈을 얻으세요

2337. 조각을 움직여 문자열을 얻으세요

난이도:중

주제: 두 포인터, 문자열

길이가 n인 두 개의 문자열 start와 target이 제공됩니다. 각 문자열은 'L', 'R' 및 '_' 문자로만 구성됩니다.

• 문자 'L'과 'R'은 조각을 나타내며, 조각 'L'은 바로 왼쪽에 빈 공간이 있는 경우에만 왼쪽으로 이동할 수 있습니다. 조각 'R'은 빈 공간이 있는 경우에만 오른쪽으로 이동할 수 있습니다. 그렇죠.
• 문자 '_'는 'L' 또는 'R' 조각 모든이 들어갈 수 있는 공백을 나타냅니다.

문자열 시작 부분을 원하는 만큼 이동하여 문자열 대상을 얻을 수 있으면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

예 1:

• 입력: 시작 = "LRR", 대상 = "L______RR"
• 출력: true
• 설명: 다음 동작을 수행하여 처음부터 문자열 대상을 얻을 수 있습니다.
  • 첫 번째 조각을 왼쪽으로 한 단계 이동하면 시작은 "L__RR"과 같습니다.
  • 마지막 조각을 오른쪽으로 한 단계 이동하면 시작은 "L_R_R"과 같습니다.
  • 두 번째 조각을 오른쪽으로 세 단계 이동하면 시작은 "L______RR"과 같습니다.
  • 처음부터 문자열 대상을 얻을 수 있으므로 true를 반환합니다.

예 2:

• 입력: 시작 = "R_L_", 대상 = "__LR"
• 출력: false
• 설명: 문자열 시작 부분의 'R' 조각은 오른쪽으로 한 단계 이동하여 "RL"을 얻을 수 있습니다.
  • 이후에는 더 이상 조각이 움직일 수 없으므로 처음부터 문자열 대상을 획득하는 것이 불가능합니다.

예 3:

• 입력: 시작 = "R", 대상 = "R"
• 출력: false
• 출력: 문자열 시작 부분의 조각은 오른쪽으로만 이동할 수 있으므로 시작 부분에서 문자열 대상을 얻는 것이 불가능합니다.

제약조건:

• n == 시작.길이 == 목표.길이
• 1 5
• start와 target은 'L', 'R', '_' 문자로 구성됩니다.

힌트:

1. 몇 번의 이동 후에 조각 순서가 바뀔 수 있나요?
2. s의 각 조각을 e의 조각과 연결해 보세요.

해결책:

주어진 규칙에 따라 조각('L' 및 'R')을 이동하여 문자열 시작을 문자열 대상으로 변환할 수 있는지 확인해야 합니다. 고려해야 할 주요 제약 사항은 다음과 같습니다.

• 'L'은 왼쪽으로만 이동할 수 있습니다(다른 'L' 또는 'R' 조각과 교차할 수 없음).
• 'R'은 오른쪽으로만 이동할 수 있습니다(다른 'L' 또는 'R' 조각은 교차할 수 없습니다).
• 공백('_')을 사용하여 조각을 이동할 수 있습니다.

계획:

1. 길이 확인: 먼저 두 문자열의 길이가 같은지 확인하세요. 그렇지 않은 경우 즉시 false를 반환합니다.

2. 문자 빈도 확인: 조각이 복제되거나 파괴될 수 없으므로 시작 문자열의 'L', 'R' 및 '_' 개수는 대상 문자열의 해당 개수와 일치해야 합니다. , 이사만 했습니다.

3. 두 포인터를 사용한 조각 일치:

   • 두 문자열(시작 및 대상)을 통과합니다.
   • 시작의 각 조각('L' 또는 'R')이 대상의 해당 위치로 이동할 수 있는지 확인하세요.
   • 구체적으로:
     • 'L'은 항상 왼쪽으로 움직여야 합니다(즉, 대상의 말이 오른쪽으로 움직여야 하는 위치에 있어서는 안 됩니다).
     • 'R'은 항상 오른쪽으로 이동해야 합니다(즉, 대상의 말이 왼쪽으로 이동해야 하는 위치에 있어서는 안 됩니다).

알고리즘 설명:

1. L 및 R 위치 필터링:

   • L과 R의 순서를 비교하려면 문자열 start와 target에서 모두 _를 모두 제거하세요. 순서가 다르면 즉시 false를 반환하세요.

2. 2점 탐색:

   • 두 개의 포인터를 사용하여 시작 및 대상의 문자를 반복합니다.
   • 다음 사항을 확인하세요.
     • L의 경우 시작 부분은 왼쪽만 이동할 수 있으므로 시작 위치는 대상 위치보다 크거나 같아야 합니다.
     • R의 경우 시작 부분은 오른쪽만 이동할 수 있으므로 시작 위치는 대상 위치보다 작거나 같아야 합니다.

3. 출력 결과:

   • 순회 중에 모든 조건이 충족되면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2337. 조각을 옮겨서 끈을 얻으세요

<?php
/**
 * @param String $start
 * @param String $target
 * @return Boolean
 */
function canChange($start, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
var_dump(canChange("_L__R__R_", "L______RR")); // true
var_dump(canChange("R_L_", "__LR"));          // false
var_dump(canChange("_R", "R_"));              // false
?>

설명:

1. 초기 확인: 먼저 두 문자열의 길이를 확인하고 'L'과 'R'의 개수가 두 문자열에서 동일한지 확인합니다. 그렇지 않은 경우 false를 반환합니다.

2. 두 포인터 논리: 두 포인터 i와 j를 사용하여 두 문자열을 모두 탐색합니다.

   • 빈칸('_')은 조각의 움직임에 영향을 주지 않으므로 생략하세요.
   • start와 target의 i와 j에 있는 문자가 다른 경우 false를 반환합니다(조각을 다른 문자로 이동할 수 없으므로).
   • start에 'L'이 있고 목표 위치보다 큰 위치에 있거나, start에 'R'이 있고 목표 위치보다 작은 위치에 있는 경우 false를 반환합니다('L'이므로 '는 왼쪽으로만 움직일 수 있고, 'R'은 오른쪽으로만 움직일 수 있습니다.

3. Edge Cases: 솔루션은 다음과 같은 가능한 모든 극단적인 경우를 처리합니다.

   • 시작 및 대상의 'L' 또는 'R' 개수가 다릅니다.
   • 제약으로 인해 조각을 이동할 수 없습니다.

시간 복잡도:

• 시간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다. 이는 각 문자열을 한 번만 순회하기 때문입니다.

공간 복잡도:

• 고정된 양의 추가 공간만 사용하므로 공간 복잡도는 O(1)입니다.

복잡성 분석:

1. 시간 복잡도:

   • 밑줄 필터링에는 O(n)이 소요됩니다.
   • 2점 탐색에는 O(n)이 소요됩니다.
   • 전체: O(n).

2. 공간 복잡도:

   • 두 개의 문자열($startNoUnderscore 및 $targetNoUnderscore)이 각각 O(n) 크기로 생성됩니다.
   • 전체: O(n).

테스트 케이스 설명:

1. 입력: _L__R__R_, L______RR

   • L과 R이 일치하는 순서
   • 각 조각은 규칙에 따라 필요한 위치로 이동할 수 있습니다.
   • 출력: true.

2. 입력: R_L_, __LR

   • L과 R이 일치하는 순서
   • R 조각은 왼쪽으로 이동할 수 없습니다. 따라서 변형이 불가능합니다.
   • 출력: false.

3. 입력: _R, R_

   • R 조각은 왼쪽으로 이동할 수 없습니다. 따라서 변형이 불가능합니다.
   • 출력: false.

이 구현은 효율적이고 문제 제약 조건을 준수하므로 큰 입력 크기에 적합합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 조각을 움직여서 끈을 얻으세요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!