Giả sử chúng ta có một chuỗi chữ thường s. Chúng ta phải tìm số lượng nhỏ nhất các chuỗi con liền kề mà s được chia thành các phần sao cho mỗi chuỗi con là không tăng hoặc không giảm. Ví dụ, chuỗi "pqqqr" là không giảm, và "qqqp" là không tăng.
Vì vậy, nếu đầu vào là s = "pqrsrqp", thì đầu ra sẽ là 2, vì chúng ta có thể chia s thành "pqrs" và "rqp".
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:
nếu s rỗng, thì trả về 0
last := s[0]
direction := 1
count := 1
với mỗi char trong s, thực hiện
nếu char > last, thì
nếu direction bằng 1, thì direction := 0
ngược lại khi direction bằng 2, thì direction := 1, count := count + 1
ngược lại khi char < last, thì
nếu direction bằng 1, thì direction := 2
ngược lại khi direction bằng 0, thì direction := 1, count := count + 1
last := char
trả về count
Ví dụ
Hãy xem triển khai sau để hiểu rõ hơn:
def solve(s):
if not s:
return 0
last = s[0]
direction = 1
count = 1
for char in s:
if char > last:
if direction == 1:
direction = 0
elif direction == 2:
direction = 1
count += 1
elif char < last:
if direction == 1:
direction = 2
elif direction == 0:
direction = 1
count += 1
last = char
return count
s = "pqrsrqp"
print(solve(s))
Đầu vào
"pqrsrqp"
Đầu ra
2