순환 증분을 사용하여 문자열을 하위 시퀀스로 만들기

2825. 순환 증분을 사용하여 문자열을 하위 시퀀스로 만들기

난이도:중

주제: 두 포인터, 문자열

두 개의 인덱스가 0인 문자열 str1과 str2가 제공됩니다.

작업에서 str1의 인덱스 세트를 선택하고 세트의 각 인덱스 i에 대해 str1[i]를 다음 문자까지 주기적으로 증가시킵니다. 즉, 'a'는 'b'가 되고, 'b'는 'c'가 되고, 'z'는 'a'가 됩니다.

최대 한 번 연산을 수행하여 str2를 str1의 하위 시퀀스로 만드는 것이 가능하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

참고: 문자열의 하위 시퀀스는 나머지 문자의 상대적 위치를 방해하지 않고 문자 중 일부(아무 것도 없을 수도 있음)를 삭제하여 원래 문자열에서 형성된 새 문자열입니다.

예 1:

• 입력: str1 = "abc", str2 = "ad"
• 출력: true
• 설명: str1에서 인덱스 2를 선택합니다.
  • 'd'가 되려면 str1[2]을 증가시키세요.
  • 따라서 str1은 "abd"가 되고 str2는 이제 하위 시퀀스가 ​​됩니다. 따라서 true가 반환됩니다.

예 2:

• 입력: str1 = "zc", str2 = "ad"
• 출력: true
• 설명: str1에서 인덱스 0과 1을 선택합니다.
  • 'a'가 되려면 str1[0]을 증가시키세요.
  • 'd'가 되려면 str1[1]을 증가시키세요.
  • 따라서 str1은 "ad"가 되고 str2는 이제 하위 시퀀스가 ​​됩니다. 따라서 true가 반환됩니다.

예 3:

• 입력: str1 = "ab", str2 = "d"
• 출력: false
• 설명: 이 예에서는 최대 한 번만 작업을 사용하여 str2를 str1의 하위 시퀀스로 만드는 것이 불가능하다는 것을 알 수 있습니다.
  • 따라서 false가 반환됩니다.

제약조건:

• 1 <= str1.length <= 10⁵
• 1 <= str2.length <= 10⁵
• str1과 str2는 영문 소문자로만 구성됩니다.

힌트:

1. 따로 증가할 인덱스를 고려하세요.
2. 두 개의 포인터, 즉 str1에 대한 포인터 i와 str2에 대한 포인터 j를 유지하면서 해당 포인터가 문자열 경계 내에 유지되도록 할 수 있습니다.
3. str1[i]와 str2[j]가 모두 일치하거나 증가하는 str1[i]가 str2[j]와 일치하면 두 포인터가 모두 증가합니다. 그렇지 않으면 포인터 i만 증가합니다.
4. 더 이상 일치하는 항목을 찾을 수 없으면 j가 str2의 끝에 있는 경우 str2를 str1의 하위 시퀀스로 만드는 것이 가능합니다.

해결책:

str1의 모든 문자에 대해 최대 한 번의 순환 증분 연산을 수행하여 str2를 str1의 하위 시퀀스로 만들 수 있는지 확인해야 합니다.

설명:

• str1에는 i, str2에는 j라는 두 개의 포인터를 사용합니다.
• str1[i]의 문자가 str2[j]와 일치하면 두 포인터를 모두 앞으로 이동합니다.
• str1[i]가 str2[j]와 일치하도록 증가할 수 있는 경우(주기적으로) 이를 일치시킨 다음 두 포인터를 모두 이동합니다.
• 위 조건 중 어느 것도 성립하지 않으면 str1에 대해 포인터 i만 이동합니다.
• 마지막으로 str2의 모든 문자를 일치시킬 수 있다면 str2를 str1의 하위 시퀀스로 만드는 것이 가능합니다. 그렇지 않으면 그렇지 않습니다.

이 솔루션을 PHP: 2825로 구현해 보겠습니다. 순환 증분을 사용하여 문자열을 하위 시퀀스로 만들기

  
  
  설명:




두 포인터: i와 j는 각각 str1과 str2의 시작으로 초기화됩니다.

일치 논리: 루프 내에서 str1[i]와 str2[j]의 문자가 동일한지 또는 str1[i]를 증가시켜 str2[j]와 주기적으로 일치시킬 수 있는지 확인합니다.


순환 증분 조건은 str1[i]가 str2[j]와 일치하도록 증분될 수 있는지 확인하는 (ord($str1[$i]) 1 - ord('a')) % 26을 사용하여 처리됩니다.



하위 시퀀스 확인: str2를 완전히 반복했다면(즉, j == m) str2가 str1의 하위 시퀀스라는 의미입니다. 그렇지 않으면 그렇지 않습니다.



  
  
  시간 복잡도:



알고리즘은 str1을 한 번 반복하고 str2의 각 문자는 한 번만 확인하므로 시간 복잡도는 O(n)입니다. 여기서 n은 str1의 길이입니다.



  
  
  공간 복잡도:



공간 복잡도는 O(1)입니다. 몇 개의 포인터만 사용하고 입력 크기에 따라 추가 공간이 필요하지 않기 때문입니다.


이 솔루션은 최대 한 번의 순환 증분 연산으로 str2를 str1의 하위 시퀀스로 만드는 것이 가능한지 효율적으로 확인합니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 순환 증분을 사용하여 문자열을 하위 시퀀스로 만들기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!