[LeetCode] 777. LR String 의 인접 한 문제 풀이 보고서 스 왑 (파 이 썬)

저자: 음 설 명 초 id: fuxuemingzhu 개인 블 로그:http://fuxuemingzhu.cn/
목차
제목 설명
제목
풀이 방법
지능 문제
비슷 한 제목
참고 자료
날짜
제목 주소:https://leetcode.com/problems/swap-adjacent-in-lr-string/description/
제목 설명
In a string composed of 'L' , 'R' , and 'X' characters, like "RXXLRXRXL" , a move consists of either replacing one occurrence of "XL" with "LX" , or replacing one occurrence of "RX" with "XR" . Given the starting string start and the ending string end , return True if and only if there exists a sequence of moves to transform one string to the other.
Example:

Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: True
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Note:

1 <= len(start) = len(end) <= 10000.

Both start and end will only consist of characters in {‘L’, ‘R’, ‘X’}.

제목 의 대의
초기 문자열 의 XL 을 LX 로 바 꿀 수 있 는 초기 문자열 을 주 었 습 니 다. 초기 문자열 의 RX 를 XR 로 바 꿀 수 있 습 니 다. 일정한 횟수 를 통과 한 후에 초기 문자열 을 끝 문자열 로 바 꿀 수 있 는 지 물 어보 십시오.
문제 풀이 방법
지능 문제
미로 같은 검색 문제 인 줄 알 았 는데 데이터 규모 가 이렇게 큰 걸 보 니 안 닮 았 어 요. 태 그 를 보 니 역시 지능 문제 라 서 포 기 했 어 요. 지능 이 부족 해 요.
제목 은 초기 문자열 의 XL 을 LX 로 바 꿀 수 있 고, 초기 문자열 의 RX 를 XR 로 바 꿀 수 있다 고 했다. 그러면 초기 문자열 의 L 은 왼쪽으로 만 이동 할 수 있 고, 초기 문자열 의 R 은 오른쪽으로 만 이동 할 수 있다 는 것 이다.또한 L 과 R 은 순 서 를 바 꿀 수 없 으 며 두 문자열 의 L 과 R 은 대응 하 는 횟수 가 같 아야 합 니 다.이 규칙 을 알 고 나 면 두 바늘 로 해결 하면 된다.
i, j 로 start 와 end 의 시작 위 치 를 가리 키 고 그들 이 X 를 가리 키 면 모두 오른쪽으로 X 가 아 닌 위치 로 이동 합 니 다. 그러면 그들 이 가리 키 는 문 자 는 같 아야 합 니 다. 그렇지 않 으 면 False 로 돌아 갑 니 다.L 을 가리 키 면 start 의 L 색인 은 end 의 L 색인 보다 작 을 수 밖 에 없습니다.R 을 가리 키 면 end 의 R 색인 은 end 의 R 색인 보다 클 수 밖 에 없습니다.while 가 끝나 기 전에 i 와 j 를 동시에 뒤로 이동 해 야 합 니 다.
모든 판단 이 완료 되면 True 로 돌아 갑 니 다.
시간 복잡 도 는 O (N) 이 고 공간 복잡 도 는 O (1) 이다.

class Solution(object):
    def canTransform(self, start, end):
        """
        :type start: str
        :type end: str
        :rtype: bool
        """
        i, j = 0, 0
        N = len(start)
        while i < N and j < N:
            while i < N - 1 and start[i] == 'X':
                i += 1
            while j < N - 1 and end[j] == 'X':
                j += 1
            if start[i] != end[j]:
                return False
            if start[i] == 'L' and i < j:
                return False
            if start[i] == 'R' and i > j:
                return False
            i += 1
            j += 1
        return True

비슷 한 제목
참고 자료
http://www.cnblogs.com/grandyang/p/9001474.html
날짜.
2018 년 10 월 30 일 -- 아, 10 월 이 다 지 났 구나