leetcode-854-K-Similar Strings

王笑朝發布于2019-07-30 17:40 / 1396人閱讀

摘要：沒有發現字符串的遍歷，一種向前，一種向后。遞歸函數，利用返回結果的話，返回結果是遞歸到最后，結束遍歷以后，得到的結果才有效。

題目本質：通過將字符串A的字母之間的連續交換位置，達到 兩個字符串之間完全相同的情況
解析：通過將不相等處的字母，發現之后找到想等的，然后進行位置替換。如此反復。

   問題在于慢，慢在于只要不相等，就會遍歷字符串之后所有的字符，大量重復的無意義的計算比較，所以將遍歷過的計算過的存在于memo字符串中間。

錯誤：沒有找到效率低的問題所在，在于比較過的無意義的比較。

   沒有發現字符串的遍歷，一種向前，一種向后。
   對付效率低，一種有效的方式就是緩存，將比較過的先儲存起來

應用：緩存意識，發現大量比較，可能有重復，儲存。

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

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)

云服務器 GPU云服務器 strings

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/42347.html

Java中ArrayList remove會遇到的坑

摘要：前言平時最常用的莫過于和了，面試的時候也是問答的常客。先不去管容量負載因子什么的，就是簡單的使用也會遇到坑。元素經常遇到的一個場景是遍歷然后找到合適條件的給刪除掉，比如刪除所有的偶數。文初的做法不報錯，但結果并不是我們想要的。前言平時最常用的莫過于ArrayList和HashMap了，面試的時候也是問答的常客。先不去管容量、負載因子什么的，就是簡單的使用也會遇到坑。 showImg...

LiangJ 2019-08-15 11:58 評論0 收藏0
ES6 Features系列：Template Strings & Tagged Templ

摘要：由兩部分組成模板起始符，稱為沉音符反引號，其內容被識別為字符串模板。其實這是通過屬性操作中的結果，也就是說屬性將對控制符進行轉義從而實現按照普通字符輸出。的語法是緊跟在后面，兩者間不能有空格或制表符等。 1. Brief ES6(ECMAScript 6th edition)于2015年7月份發布，雖然各大瀏覽器仍未全面支持ES6，但我們可以在后端通過Node.js 0.12和io....

MyFaith 2019-08-21 10:34 評論0 收藏0
linux之strings命令

摘要：命令是二進制工具集的一員，用于打印文件中可打印字符串，命令在對象文件或二進制文件中查找可打印的字符串。打印字符序列的偏移量原文鏈接微信公眾號入門小站 strings 命令是二進制工具集 GNU Binutils 的一員，用于打印文件中可打印字符串，strings命令在對象文件或二進制文件中查找可打印的字符串。字...

番茄西紅柿 2021-11-24 09:38 評論0 收藏2637
Stream API和Optional類學習筆記

摘要：用于對流進行排序。三最終操作用于迭代流中的每個元素，并執行相應的操作。類類也是的新特性，用于有效解決問題。與的功能一樣，不過接受一個函數式接口來生成對象為空則拋出異常與使用類似與使用類似這是一種級聯的方式，能夠解決方式的嵌套問題。 Stream API Stream API是Java8的新特性，通常用于對集合進行一些操作，可以幫助開發者寫出更高效、整潔的代碼。一、Stream流的創建...

geekidentity 2019-08-16 18:31 評論0 收藏0