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)))
待续...
原文：https://www.cnblogs.com/Luv-GEM/p/11084731.html