สมมติว่าเรามีสตริงสองตัว A และ B เราจะหมุนสตริง A และตรวจสอบว่าตรงกับ B ในตำแหน่งใดตำแหน่งหนึ่งของการหมุนหรือไม่ ถ้าใช่ให้คืนค่า true ไม่เช่นนั้นคืนค่า false เช่น ถ้า A = 'abcde' และ B = 'bcdea' คำตอบจะเป็น true เนื่องจาก A สามารถแปลงเป็น B ได้หลังจากหมุน
วิธีการแก้ปัญหา
- เมื่อ A และ B ทั้งคู่ว่าง ให้คืนค่า true เมื่อความยาวต่างกัน ให้คืนค่า false
- A := ต่อ A เข้ากับ A เอง (A = A * 2)
- i := 0, และ j := 0
- while i < ความยาวของ A:
- ถ้าความยาวของ A - i + 1 < ความยาวของ B ให้คืนค่า false
- while i < ความยาวของ A และ j < ความยาวของ B และ A[i] = B[j]:
- เพิ่ม i และ j ขึ้น 1
- ถ้า j = ความยาวของ B ให้คืนค่า true
- ถ้า j ไม่ใช่ 0 ให้ลด i ลง 1
- j := 0
- เพิ่ม i ขึ้น 1
ตัวอย่างโค้ด
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"))
อินพุต
"abcde" "cdeab"
เอาต์พุต
True
