Giả sử chúng ta có hai chuỗi s và t, chúng ta phải kiểm tra xem s có thể chuyển thành t trong k lần di chuyển hoặc ít hơn hay không. Trong lần di chuyển thứ i, bạn có thể thực hiện các thao tác này.
-
Chọn bất kỳ chỉ mục j (bắt đầu từ 1) trong s, sao cho 1 <=j <=size của s và j chưa được chọn trong bất kỳ lần di chuyển nào trước đó và dịch chuyển ký tự ở chỉ mục thứ i đó số lần.
-
Giữ nguyên như hiện tại.
Ở đây, việc thay đổi một ký tự có nghĩa là thay thế nó bằng ký tự tiếp theo trong bảng chữ cái (nếu ký tự là 'z', thì chuyển nó thành 'a'). Vì vậy, việc dịch chuyển một ký tự lên i lần cho thấy việc áp dụng các hoạt động dịch chuyển i lần.
Vì vậy, nếu đầu vào là s ="poput" t ="vwput" k =9, thì đầu ra sẽ là Đúng vì tại i =6, chúng ta có thể chuyển đổi 'p' thành 'v' và tại i =8, chúng ta có thể chuyển đổi 'o' thành 'w'.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
-
nếu kích thước của s không giống với kích thước của t, thì
-
trả về Sai
-
-
count:=một mảng nắm giữ (tối thiểu là 1 và (k - i + 1 + (k - i) / 26)) cho tất cả i từ 0 đến 25
-
đối với mỗi ký tự c1 từ s và c2 từ t, thực hiện
-
nếu c1 không giống với c2 thì
-
diff:=(ASCII của c2 - ASCII của c1 + 26) mod 26
-
nếu đếm [diff] <=0, thì
-
trả về Sai
-
-
count [diff]:=count [diff] - 1
-
-
-
trả về True
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
Ví dụ
def solve(s, t, k): if len(s) != len(t): return False count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)] for c1, c2 in zip(s, t): if (c1 != c2): diff = (ord(c2) - ord(c1) + 26) % 26 if count[diff] <= 0: return False count[diff] -= 1 return True s = "poput" t = "vwput" k = 9 print(solve(s, t,k))
Đầu vào
"poput","vwput",9
Đầu ra
True