Xoay chuỗi trong Python

Cho hai chuỗi A và B. Xoay chuỗi A và kiểm tra xem có vị trí nào khớp với B không. Nếu có trả về true, ngược lại false. Ví dụ: A = 'abcde', B = 'bcdea' → true vì xoay A được B.

Giải pháp

Các bước:

• Nếu cả A và B rỗng → true; nếu độ dài khác nhau → false.
• Nối A với chính nó: A = A*2.
• Duyệt với hai con trỏ i, j để tìm B trong A*A.

Ví dụ

Triển khai Python:

class Solution(object): 
    def rotateString(self, A, B): 
        if not A and not B: 
            return True 
        if len(A) != len(B): 
            return False 
        A = A*2 
        i = 0 
        j=0 
        while i < len(A): 
            if len(A)-i+1<len(B): 
                return False 
            while i<len(A) and j < len(B) and A[i] == B[j]: 
                i+=1 
                j+=1 
            if j == len(B): 
                return True 
            if j: 
                i-=1 
            j=0 
            i+=1 
ob1 = Solution() 
print(ob1.rotateString("abcde", "cdeab"))

Đầu vào

"abcde" "cdeab"

Đầu ra

True