如果我有 2 個字符串s1和s2，其中s2是循環(huán)移位的字符串s1。s1它需要找到從到的最小可能循環(huán)偏移s2。讓我舉個例子：s1 = 'I love cookies 's2 = 'cookies I love ' 答案是7。最好采用線性時間。有我失敗的試驗(yàn)：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. 因?yàn)樗饕瘮?shù)只返回我第一次出現(xiàn)的字母。請至少給我一個邏輯來編碼它。
1 回答
拉丁的傳說
TA貢獻(xiàn)1789條經(jīng)驗(yàn) 獲得超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不是 的循環(huán)移位，將打印s1）。
它起作用的原因是如果s2確實(shí)是 的循環(huán)移位s1，那么連接s1到自身將包含s2中間的某個地方。
s1幸運(yùn)的是，這個“某處”正好是所需移位的大?。ǔ霈F(xiàn)在s2第一個字符之前的字符數(shù)）。
我們還需要檢查“其他方向”以獲得可能更短的移位，因此我們從兩個可能的方向獲取最小結(jié)果（技術(shù)上可以使用算術(shù)來避免第二次搜索，如果結(jié)果是那么答案很簡單 -> n/2結(jié)果n。
關(guān)于運(yùn)行時復(fù)雜性的注意事項：我的解決方案不保證線性時間，基于這個答案，它可以O(shè)(N*N)在最壞的情況下使用。
添加回答
舉報
0/150
提交
取消