77.Longest Common Subsequence https://www.lintcode.com/problem/longest-common-subsequence/description?_from=ladderfromId=16 public class Solution { /** * @param A: A string * @param B: A string * @return : The length of longest common subse
77. Longest Common Subsequence
https://www.lintcode.com/problem/longest-common-subsequence/description?_from=ladder&&fromId=16
public class Solution { /** * @param A: A string * @param B: A string * @return: The length of longest common subsequence of A and B */ public int longestCommonSubsequence(String A, String B) { // write your code here char[] s1 = A.toCharArray(); char[] s2 = B.toCharArray(); int m = s1.length; int n = s2.length; int[][] f = new int[m+1][n+1]; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(i==0){ f[i][j] =0; continue; } if(j==0){ f[i][j] =0; continue; } f[i][j] = Math.max(f[i-1][j],f[i][j-1]); if(s1[i-1]== s2[j-1]){ f[i][j] = Math.max(f[i][j],f[i-1][j-1]+1); } } } return f[m][n]; } }View Code
119. Edit Distance
https://www.lintcode.com/problem/edit-distance/description?_from=ladder&&fromId=16
public class Solution { /** * @param word1: A string * @param word2: A string * @return: The minimum number of steps. */ public int minDistance(String word1, String word2) { // write your code here char [] A = word1.toCharArray(); char [] B = word2.toCharArray(); int m = A.length; int n = B.length; int[][] f = new int[m+1][n+1]; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(i==0){ f[i][j]= j; continue; } if(j==0){ f[i][j] = i; continue; } f[i][j] = Math.min(Math.min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1; if(A[i-1]==B[j-1]){ f[i][j]= Math.min(f[i][j],f[i-1][j-1]); } } } return f[m][n]; } }View Code
滚动数组优化
public class Solution { /** * @param word1: A string * @param word2: A string * @return: The minimum number of steps. */ public int minDistance(String word1, String word2) { // write your code here char [] A = word1.toCharArray(); char [] B = word2.toCharArray(); int m = A.length; int n = B.length; int[][] f = new int[2][n+1]; int old,now=0; for(int i=0;i<=m;i++){ old = now; now = 1-now; for(int j=0;j<=n;j++){ if(i==0){ f[now][j]= j; continue; } if(j==0){ f[now][j] = i; continue; } f[now][j] = Math.min(Math.min(f[old][j],f[now][j-1]),f[old][j-1])+1; if(A[i-1]==B[j-1]){ f[now][j]= Math.min(f[now][j],f[old][j-1]); } } } return f[now][n]; } }View Code
29. Interleaving String
https://www.lintcode.com/problem/interleaving-string/description?_from=ladder&&fromId=16
public class Solution { /** * @param s1: A string * @param s2: A string * @param s3: A string * @return: Determine whether s3 is formed by interleaving of s1 and s2 */ public boolean isInterleave(String s1, String s2, String s3) { // write your code here if(s1.length()+s2.length()!=s3.length()){ return false; } int m = s1.length(); int n = s2.length(); boolean[][] f = new boolean[m+1][n+1]; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(i==0 && j==0){ f[i][j] = true; continue; } f[i][j] = false; if(i>0 && s1.charAt(i-1)==s3.charAt(i+j-1) && f[i-1][j]){ f[i][j] = true; } if(j>0 && s2.charAt(j-1) == s3.charAt(i+j-1) && f[i][j-1]){ f[i][j] = true; } } } return f[m][n]; } }View Code
54. Regular Expression Matching
https://www.lintcode.com/problem/regular-expression-matching/description?_from=ladder&&fromId=16
public class Solution { /** * @param s: A string * @param p: A string includes "." and "*" * @return: A boolean */ public boolean isMatch(String s, String p) { // write your code here char[] A = s.toCharArray(); char[] B = p.toCharArray(); int m = A.length; int n = B.length; boolean[][] f = new boolean[m+1][n+1]; for(int i =0;i<=m;i++){ for(int j =0;j<=n;j++){ if(i==0 && j==0){ f[i][j] = true; continue; } //空正则无法匹配有长度字符串 if(j==0){ f[i][j] = false; continue; } f[i][j] = false; if(B[j-1]!=‘*‘){ if(i>0 && (B[j-1]==‘.‘||A[i-1]==B[j-1])){ f[i][j] = f[i-1][j-1]; } }else{ if(j>1){ f[i][j] = f[i][j-2]; } if(i>0 && j>1 && (B[j-2]==‘.‘ || A[i-1]==B[j-2])){ f[i][j] = f[i-1][j]|f[i][j-2]; } } } } return f[m][n]; } }View Code
详细解析版：在B的结尾为.*或者a[i-1]*的情况下 注意是f[i][j]= f[i-1][j]|f[i][j-2] 这一句很重要，之前写成了f[i][j]= f[i-1][j]，这样子就忽略了*只匹配0字符的情况
public class Solution { /** * @param s: A string * @param p: A string includes "." and "*" * @return: A boolean */ public boolean isMatch(String s, String p) { // write your code here char[] A = s.toCharArray(); char[] B = p.toCharArray(); int m = A.length; int n = B.length; boolean[][] f = new boolean[m+1][n+1]; for(int i =0;i<=m;i++){ for(int j =0;j<=n;j++){ if(i==0 && j==0){ f[i][j] = true; continue; } //空正则无法匹配有长度字符串 if(j==0){ f[i][j] = false; continue; } f[i][j] = false; //B结尾为字母 if(B[j-1]!=‘.‘ && B[j-1]!=‘*‘ && i>0 && A[i-1]==B[j-1]){ f[i][j] = f[i-1][j-1]; continue; } //B结尾为. if(B[j-1]==‘.‘ && i>0){ f[i][j] = f[i-1][j-1]; continue; } //B结尾为* if(B[j-1]==‘*‘ && j>=2){ //A为空串 if(i==0){ f[i][j] = f[i][j-2]; }else{ if(B[j-2]==‘.‘){ f[i][j] = f[i-1][j]|f[i][j-2]; }else if(B[j-2]==A[i-1]){ f[i][j]= f[i-1][j]|f[i][j-2]; }else{ f[i][j] = f[i][j-2]; } } } } } return f[m][n]; } }View Code
192. Wildcard Matching
https://www.lintcode.com/problem/wildcard-matching/description?_from=ladder&&fromId=16
public class Solution { /** * @param s: A string * @param p: A string includes "?" and "*" * @return: is Match? */ public boolean isMatch(String s, String p) { // write your code here int m = s.length(); int n = p.length(); boolean[][] f = new boolean[m+1][n+1]; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ f[i][j] = false; if(i==0 && j==0){ f[i][j] = true; continue; } if(j==0){ continue; } if((i>0) && (p.charAt(j-1)==‘?‘ || s.charAt(i-1)==p.charAt(j-1))){ f[i][j] = f[i-1][j-1]; continue; } if(p.charAt(j-1) == ‘*‘){ if(i==0){ f[i][j] = f[i][j-1]; }else{ f[i][j] = f[i][j-1] || f[i-1][j] || f[i-1][j-1]; } } } } return f[m][n]; } }View Code
668. Ones and Zeroes
https://www.lintcode.com/problem/ones-and-zeroes/description?_from=ladder&&fromId=16
public class Solution { /** * @param strs: an array with strings include only 0 and 1 * @param m: An integer * @param n: An integer * @return: find the maximum number of strings */ public int findMaxForm(String[] strs, int m, int n) { // write your code here if(strs==null || strs.length ==0){ return 0; } int count = strs.length; // 每个01串包含的0和1个数 int[] cnt0 = new int[count]; int[] cnt1 = new int[count]; for(int i = 0;i<strs.length;i++){ if(strs[i] == null || strs[i].length()==0){ continue; } char[] arrays = strs[i].toCharArray(); for(int j=0;j<arrays.length;j++){ if(arrays[j]==‘0‘){ cnt0[i]++; }else{ cnt1[i]++; } } } //由多少个0 多少个1 可以构成 前多少个串 int[][][] f = new int[m+1][n+1][count+1]; for(int c=0;c<=count;c++) for(int i =0;i<=m;i++) for(int j =0;j<=n;j++){ if(c==0){ f[i][j][c] =0; continue; } f[i][j][c] = f[i][j][c-1]; //如果最后一个串可以构成，可以扣掉最后一个串的0和1继续递推前c-1个串 if(i>=cnt0[c-1] && j>=cnt1[c-1]){ f[i][j][c] = Math.max(f[i][j][c],f[i-cnt0[c-1]][j-cnt1[c-1]][c-1]+1); } } return f[m][n][count]; } }View Code
滚动数组优化
public class Solution { /** * @param strs: an array with strings include only 0 and 1 * @param m: An integer * @param n: An integer * @return: find the maximum number of strings */ public int findMaxForm(String[] strs, int m, int n) { // write your code here if(strs==null || strs.length ==0){ return 0; } int count = strs.length; // 每个01串包含的0和1个数 int[] cnt0 = new int[count]; int[] cnt1 = new int[count]; for(int i = 0;i<strs.length;i++){ if(strs[i] == null || strs[i].length()==0){ continue; } char[] arrays = strs[i].toCharArray(); for(int j=0;j<arrays.length;j++){ if(arrays[j]==‘0‘){ cnt0[i]++; }else{ cnt1[i]++; } } } //由多少个0 多少个1 可以构成 前多少个串 int[][][] f = new int[m+1][n+1][count+1]; int old,now =0; for(int c=0;c<=count;c++){ old = now; now = 1- now; for(int i =0;i<=m;i++) for(int j =0;j<=n;j++){ if(c==0){ f[i][j][now] =0; continue; } f[i][j][now] = f[i][j][old]; //如果最后一个串可以构成，可以扣掉最后一个串的0和1继续递推前c-1个串 if(i>=cnt0[c-1] && j>=cnt1[c-1]){ f[i][j][now] = Math.max(f[i][j][now],f[i-cnt0[c-1]][j-cnt1[c-1]][old]+1); } } } return f[m][n][now]; } }View Code
118. Distinct Subsequences
https://www.lintcode.com/problem/distinct-subsequences/description?_from=ladder&&fromId=16
public class Solution { /** * @param S: A string * @param T: A string * @return: Count the number of distinct subsequences */ public int numDistinct(String S, String T) { // write your code here char[] s = S.toCharArray(); char[] t = T.toCharArray(); int m = s.length; int n = t.length; if(m<n){ return 0; } int[][] f = new int[m+1][n+1]; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(j==0){ f[i][j] = 1; continue; } if(i==0){ continue; } f[i][j] = f[i-1][j]; if(j>=1 && s[i-1]==t[j-1]){ f[i][j] += f[i-1][j-1]; } } } return f[m][n]; } }View Code
滚动数组优化
public class Solution { /** * @param S: A string * @param T: A string * @return: Count the number of distinct subsequences */ public int numDistinct(String S, String T) { // write your code here char[] s = S.toCharArray(); char[] t = T.toCharArray(); int m = s.length; int n = t.length; if(m<n){ return 0; } int[][] f = new int[m+1][n+1]; int now = 0; int old =0; for(int i=0;i<=m;i++){ old = now; now = 1-now; for(int j=0;j<=n;j++){ if(j==0){ f[now][j] = 1; continue; } if(i==0){ continue; } f[now][j] = f[old][j]; if(j>=1 && s[i-1]==t[j-1]){ f[now][j] += f[old][j-1]; } } } return f[now][n]; } }View Code