萬萬沒想到之聰明的編輯
題目描述
我叫王大錘,是一家出版社的編輯。我發現一個發現拼寫錯誤的捷徑:
1. 三個同樣的字母連在一起,一定是拼寫錯誤,去掉一個的就好啦:比如 helllo -> hello
2. 兩對一樣的字母(AABB型)連在一起,一定是拼寫錯誤,去掉第二對的一個字母就好啦:比如 helloo -> hello
3. 上面的規則優先“從左到右”比對,即如果是AABBCC,雖然AABB和BBCC都是錯誤拼寫,應該優先考慮修複AABB,結果為AABCC
請聽題:請實作大錘的自動校對程式
輸入描述:
第一行包括一個數字N,表示本次用例包括多少個待校驗的字元串。
後面跟随N行,每行為一個待校驗的字元串。
輸出描述:
N行,每行包括一個被修複後的字元串。
1 N = int(input())
2 for x in range(N):
3 string = input().strip()
4 n = len(string)
5 temp = ''
6 samecount = 0
7 i = 0
8 while i < n:
9 if i == n - 1:
10 temp += string[i]
11 i += 1
12 elif i + 1 < n and string[i] != string[i + 1]:
13 temp += string[i]
14 i += 1
15 else:#s[i] == s[i+1]
16 j = i + 1
17 temp += string[i] + string[j]
18 base = string[i]
19 while j < n and base == string[j]:
20 j += 1
21 #s[j] is different from s[i]
22 if j == n:
23 break
24 else:
25 temp += string[j]
26 base2 = string[j]
27 k = j + 1
28 while k < n and base2 == string[k]:
29 k += 1
30 i = k
31 print(temp)
算法思路:滑動視窗。
在視窗内部“捕捉”以下兩種類型的子串:
1. 連續3個(含)以上相同的字元。處理辦法:隻保留2個字元。
2. 連續2個字元之後,出現的連續2個(含)以上的相同字元。處理辦法:隻保留1個字元。
捕捉完這兩種之後,進行視窗向右平移(更新i值)。
注意判斷邊界條件不要越界。