leetcode-854-K-Similar Strings

王笑朝发布于2019-07-30 17:40 / 1207人阅读

摘要：没有发现字符串的遍历，一种向前，一种向后。递归函数，利用返回结果的话，返回结果是递归到最后，结束遍历以后，得到的结果才有效。

题目本质：通过将字符串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)

服务器托管海外云主机 strings

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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