如果我有 2 個字符串s1和s2，其中s2是循環移位的字符串s1。s1它需要找到從到的最小可能循環偏移s2。讓我舉個例子：s1 = 'I love cookies 's2 = 'cookies I love ' 答案是7。最好采用線性時間。有我失敗的試驗：def find_minimum_cyclic_shift(s1, s2): if len(s1) != len(s2): return -1 index = s2.index(s1[0]) if (index > -1): if (s1==s2): return 0; #finalPosition = len(s2) - index #print(finalPosition, " index=",index) #return s2[0] == s1[finalPosition] and s1[finalPosition::]==s2[0:index] return index但它不適用于 case: absabsabsfand absfabsabs。而不是 4 我有 0. 因為索引函數只返回我第一次出現的字母。請至少給我一個邏輯來編碼它。
1 回答
拉丁的傳說
TA貢獻1789條經驗 獲得超8個贊
find您可以簡單地在雙字符串上使用，如下所示：
s1 = 'I love cookies '
s2 = 'cookies I love '
answer = min((s1*2).find(s2), (s2*2).find(s1))
print(answer)
輸出：
7
-1（如果s2不是 的循環移位，將打印s1）。
它起作用的原因是如果s2確實是 的循環移位s1，那么連接s1到自身將包含s2中間的某個地方。
s1幸運的是，這個“某處”正好是所需移位的大小（出現在s2第一個字符之前的字符數）。
我們還需要檢查“其他方向”以獲得可能更短的移位，因此我們從兩個可能的方向獲取最小結果（技術上可以使用算術來避免第二次搜索，如果結果是那么答案很簡單 -> n/2結果n。
關于運行時復雜性的注意事項：我的解決方案不保證線性時間，基于這個答案，它可以O(N*N)在最壞的情況下使用。
添加回答
舉報
0/150
提交
取消