标签为 [字符串] 的文章

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

题目: 现在有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,str2长度为N, * aim由str1和str2组成,所以长度为M+N,如果长度不对的话返回false,生成m+1,n+1大小的Boolean类型dp矩阵, * dp[i][j]的值代表aim[0 ......

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

题目描述: 给定两个字符串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=10,从”abc”编辑到”adc”,先删除b再插入d代价最小,为8; /* * 首先生成M+1,N+1的dp矩阵,dp[i][j]代表str1[0…i-1]编辑成s ......

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

题目 给定两个字符串,求解这两个字符串的最长公共子序列(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[i][j]的含义:str1[0…i]和str2[0…j]的最长公共子序列的长度 * 从左到右,从上到下,计算dp矩阵 * 1.dp第一列即dp[0…M-1][0],dp[i][0]的含义是str1[0..i]和str2[0]的最长公共子序列的长度 * str ......

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

题目: 给定两个字符串,求出它们之间最长的相同子字符串的长度。 1234567891011121314/*  * 公共子串需要连续,公共子序列不需要连续  * 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;  * 其他位置从左到右,从上到下计算,dp矩阵有以下两种情况:  * a.如果str1[i]!=str2[j],说明在必须把str1[i]和str2[j]当做公共子串的最后一个字符是不可能的,所以dp[i][j]=0;  * b.如 ......

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

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

面试指南——最小包含子串的长度

str1 和 str2 求str1 的子串 中含有str2 的所有字符的最小字串长度 例如: str1 =”abcde” str2=”ac” 返回3 /* * 最小包含子串 * 1.字符串a,b长度检查并转换成字符数组,同时新建一个长度256的int数组 * 2.遍历b数组,b数组每个元素对应的ascii码所对应的int数组++,例如acb遍历完后abc的ascii所对应的下标的位置值为1; * 3.初始化left=0,right=0,match=b.length,表示:左右目前都是0,match为字符串a目前欠字符串b多少字符, * 初始化minlen为Integer最小值,表示最小包含子串的长度。 * 4. ......

面试指南——公式字符串求值

公式字符串求值 给定一个字符串str, str表示一个公式,公式里可能有整数、加减乘除符号和左右括号,返回公式的计算结果。 可以认为给定的字符串一定是正确的公式,即不需要对str做公式有效性检查。 如果是负数,就需要用括号括起来,比如”4*(-3)”。但如果负数作为公式的开头或括号部分的开头,则可以没有括号,比如”-3*4”和”(-3*4)”都是合法的。 不用考虑计算过程中会发生溢出的情况。 /* * 1.从左到右遍历str,开始遍历或者遇到字符时,就进行递归过程。当发现str遍历完,或者遇到字符’)’时,递归过程就结束。 ......

面试指南——去掉字符串中连续出现k个0的子串

题目: 给定一个字符串str和一个整数k,如果str中正好有连续的k个’0’字符出现时,把k个连续的’0’字符去除,返回处理后的字符串。 举例: str=”A00B”,k=2,返回”A002″; str=”A0000B000″,k=3,返回”A0000B” /* * 1.设定count = 0,start = -1,count为当前连续0的数量,start为当前连续0的开始位置 * 2.从头开始遍历,如果当前为0,count++,start进行更新操作,否则的话判断当前count是否为k,则表示从当前的start开始的k个位置可以去掉 * 将其位置赋 ......