面试指南——字符串的交错组成

题目: 现在有3个字符串s1,s2,s3,我们需要判断s3是否是由s1和s2交错组成的。对于三个字符串A,B,C。我们称C由A和B交错组成当且仅当C包含且仅包含A,B中所有字符,且对应的顺序不改变 例如s1="abc",s="1234d",s3="ab1234dc",那么s3是由s1和s2交错组成的,如果s3="ab1234cd",则s3不是由s1和s2交错组成的。 /* * str1长度为M,s

- 阅读全文 -

面试指南——最小编辑代价

题目描述: 给定两个字符串str1和str2,再给定三个整数ic,dc,rc,分别代表插入、删除、替换一个字符的代价,返回将str1编辑成str2的最小代价。 举例: str1="abc" str2="adc" ic=5 dc=3 rc=2,从"abc"编辑到"adc"把b替换成d代价最小,为2; str1="abc" str2="adc" ic=5 dc=3 rc

- 阅读全文 -

面试指南——最长公共子序列问题

题目 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB 则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA /* * 以下dp[0...M-1]相当于dp[0]~dp[M-1] * str1.length = M;str2.length = N ==>生成M*N大小的dp矩阵,

- 阅读全文 -

面试指南——最长公共子串问题

题目: 给定两个字符串,求出它们之间最长的相同子字符串的长度。 /* * 公共子串需要连续,公共子序列不需要连续 * dp矩阵第一列dp[0...M-1][0],如果str1[i]==str2[0],令dp[i][0]=1,否则dp[i][0]=0; * dp矩阵第一行dp[0][0...N-1],如果str1[0]==str2[j],令dp[0][j]=1,否则dp[0][j]=0;

- 阅读全文 -

面试指南——回文最小分割数

题目:给定一个字符串str,返回把str全部切成回文子串的最小分割数。举例:str="ABA" ,不需要切割,返回0;str="ACDCDCDAD",最少需要切两次,比如"A","CDCDC","DAD",所以返回2. /* * 左成云代码分析: * 鲁棒性,初始化一个长宽为str.length()的二维数组,初始化min=Integer的最小值,初始化长度str.length的dp数组

- 阅读全文 -