字符串题汇总(python3)

1、最小编辑距离

假设有两个字符串s1和s2，计算通过增添、删除、替换三种操作后，从s1转变为s2所需要的操作次数。

#coding=utf-8

class Solution:

    def editDist(self,s1,s2):

        m,n=len(s1)+1,len(s2)+1

        matrix = [[0]*n for i in range(m)]

        matrix[0] = [i for i in range(n)]

        for i in range(m):

            matrix[i][0] = i

        for i in range(1,m):

            for j in range(1,n):

                if s1[i-1] == s2[j-1]:

                    temp = 0

                else:

                    temp = 1

                matrix[i][j] = min(matrix[i][j-1]+1,matrix[i-1][j]+1,matrix[i-1][j-1]+temp)

        return matrix[m-1][n-1]

2、替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

# -*- coding:utf-8 -*-

class Solution:

    def replaceSpace(self, s):

        temp = []

        for i in s:

            if i != ' ':

                temp.append(i)

            else:

                temp.append('%20')

        return ''.join(temp)

3、字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

这也是个神题目，思路没怎么看懂。

# -*- coding:utf-8 -*-

class Solution:

    def Permutation(self, ss):

        lens = len(ss)

        if lens == 0:

            return []

        if lens == 1:

            return [ss]

        sl = []

        for i in range(lens):

            for j in self.Permutation(ss[:i]+ss[i+1:]):

                sl.append(ss[i]+j)

        return sorted(list(set(sl)))

待续...

巴特西

字符串题汇总(python3)

最新文章

热门文章