leetcode-854-K-Similar Strings

王笑朝發(fā)布于2019-07-30 17:40 / 1403人閱讀

摘要：沒(méi)有發(fā)現(xiàn)字符串的遍歷，一種向前，一種向后。遞歸函數(shù)，利用返回結(jié)果的話，返回結(jié)果是遞歸到最后，結(jié)束遍歷以后，得到的結(jié)果才有效。

題目本質(zhì)：通過(guò)將字符串A的字母之間的連續(xù)交換位置，達(dá)到 兩個(gè)字符串之間完全相同的情況
解析：通過(guò)將不相等處的字母，發(fā)現(xiàn)之后找到想等的，然后進(jìn)行位置替換。如此反復(fù)。

   問(wèn)題在于慢，慢在于只要不相等，就會(huì)遍歷字符串之后所有的字符，大量重復(fù)的無(wú)意義的計(jì)算比較，所以將遍歷過(guò)的計(jì)算過(guò)的存在于memo字符串中間。

錯(cuò)誤：沒(méi)有找到效率低的問(wèn)題所在，在于比較過(guò)的無(wú)意義的比較。

   沒(méi)有發(fā)現(xiàn)字符串的遍歷，一種向前，一種向后。
   對(duì)付效率低，一種有效的方式就是緩存，將比較過(guò)的先儲(chǔ)存起來(lái)

應(yīng)用：緩存意識(shí)，發(fā)現(xiàn)大量比較，可能有重復(fù)，儲(chǔ)存。

   遞歸函數(shù)，利用返回結(jié)果的話，返回結(jié)果是遞歸到最后，結(jié)束遍歷以后，得到的結(jié)果才有效。

import sys
class Solution:
    def kSimilarity(self, A, B):
        memo=dict()
        self.ans=sys.maxsize
        def helper(a,b):
            if len(a)!=len(b):
                return 0
            elif a==b:
                return 0
            elif (a,b) in memo:
                print(a,b,memo[(a,b)])
                return memo[(a,b)]
            elif a[-1]==b[-1]:
                self.ans=min(self.ans,helper(a[:-1],b[:-1]))
            else:
                for i in range(0,len(a)-1):
                    # print(a,b)
                    if a[i]==b[-1]:
                        # print(a[:i],b[-1],a[i+1:])
                        a_new=a[:i]+a[-1]+a[i+1:-1]
                        # print(a_new,b[:-1])
                        self.ans=min(self.ans,1+helper(a_new,b[:-1]))
                        # self.ans=1+helper(a_new,b[:-1])
                        # break
                        # print(self.ans)
            memo[(a,b)]=self.ans
            return self.ans
        self.ans=helper(A,B)
        return self.ans

if __name__=="__main__":
    A = "aabc"
    B = "abca"
    A="abbcac"
    B="abcbca"
    A="abccaacceecdeea"
    B="bcaacceeccdeaae"
    A="fffeaacbdbdafcfbbafb"
    B="abcbdfafffefabdbbafc"
    # A="abfdfacbd b d a f cfbbafb"
    # B="abcbdfaff f e f a bdbbafc"
    # A="abccab"
    # B="abccab"
    st=Solution()
    # out=st.kSimilarity(A,B)
    out=st.kSimilarity(A,B)
    print(out)