STR [I :] = STR [I :] STR [I :]

STR [I :] represents the entire string starting with the subscript I and ending at the end

The sample

The longest common subsequence length

Given two strings A:HIEROGLYPHOLOGY and string B:MICHAELANGELO, their longest common subsequence is

HIEROGLYPHOLOGY <–> MICHAELANGELO

The longest common subsequence length is 5. Analysis is as follows:

  • If the first character of string A is exactly the same as the first character of string B, then this character must belong to the oldest sequence. The rest of the string is A[1:] and B[1:], and the final result is to add the longest length of the remaining part to the previous result
  • If the first character of two strings A and B is different, the longest common subsequence contains either the first character in A, the first character in B, or neither. The longest public string you are either A [1] and [0:] B, either A [0:] and B [1], so the longest public string is A [1] and B [0:], A [0:] and B [1] between the maximum

The final result to be calculated is dp(a.length ()-1, b.Length ()-1). The longest common subsequence length of strings A and B. Let’s say that the input string A is HIE and B is MCHI, and the goal is to compute dp(2,3).

2 represents the last index of the string A, and 3 represents the last index of the string B

The abscissa represents the last character in string A involved in calculating the length of the longest common subsequence; The ordinate represents the last character in string B involved in calculating the length of the longest common subsequence

  1. Compare the first character of A and B first, see unequal, perform unequal logic, so the largest common subsequence is either A[1:] and B[0:], or A[0:] and B[1:], or A[1:] and B[1:].

X represents the beginning of the remaining subcharacters to be compared

  1. In the case of A[1:] and B[0:], the initial letter is still different, and the largest common subsequence is either A[2:]B[0:] or A[1:] and B[1:].

  • Indicates that this branch is not written in the current diagram and only looks at the selected branch execution path
  1. For example, A[1:] and B[1:] still have different initial letters. The longest string is either A[1:]B[2:] or A[2:]B[1:]. Considering that this is only A substring, the longest common string of A and B ending with subscript 1, respectively, is computed. The maximum value of A[1]B[0] and A[0]B[1] can be determined by calculating A[0]B[1]

  1. Take A[1:]B[2:] as an example, A[1] is not equal to B[2], and the longest sequence it needs to calculate is A[1:]B[3:] or A[2]B[2]. Similarly, to calculate the maximum length of the subsequence of the string ending with 1 in A and the string ending with 2 in B, we should first look at the value of A[0]B[2]

  1. Take A[1:]B[3:] as an example, A[1] is the same as B[3], but A[0]B[3] needs to be calculated.

Process can be seen from the above analysis, to calculate the value of the corresponding position, must first put values are ready, before it can continue, that is to say, if has calculated, before you can use it to continue, otherwise can only come back to calculate it again, so don’t bargain, in that case, you can according to the abscissa from 0, populate the data line.

When A takes subscript 0, there is only 1 letter to compare with the whole string of B; when A takes subscript 1, there is A[0:1] to compare with B. The corresponding operation sequence is as follows

Public int longestCommonSubsequence(String A, String B) {// This parameter is returned in special casesif(A==null || "".equals(A) || B==null || "".equals(B)){
            return0; } int length=0; int [][] arr=new int[A.length()+1][B.length()+1]; The reason for starting at 1 is that as long as the current one is the same, the next one is at least the same. If you start at 0, you need extra logic to ensure line 0 is correct. If you start at 1, you can make good use of existing logic without having to write too much redundant codefor(int i=1; i<=A.length(); i++){for(int j=1; j<=B.length(); j++){if(A.charAt(i-1)==B.charAt(j-1)){
                   arr[i][j]=arr[i-1][j-1]+1;
               }else{ arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]); }}}return arr[A.length()][B.length()];
        
    }
Copy the code

Edit distance

For the two strings word1 and word2, find the minimum number of steps to make word1 become word2. The operations that can be used include

  • Insert a character
  • Delete a character
  • Replace a character

For example, it takes at least 3 steps for “mart” to become “karma”. From the longest common string idea above, it can be analogous that to change one string into another, the three possibilities should be minimized according to the three operations provided. Given strings A and B, A becomes B by starting with the first character

  • If A[0]==B[0], there is no need to change dp[0,0]=dp[-1,-1]; otherwise, dp[0,0]= DP [-1,-1]+1
  • Delete the first character of A and observe the rest,dp[0,0]=dp[-1,0]
  • Dp [0,0]=dp[0,-1]

Also use dp said starting from 0 subscript, need to compute the minimum value of the above three conditions, the smallest value of the array itself begins with 0, then start from 1 represents a character all have no, obviously this edit distance is another some length, it also makes the initial value is established, the resulting program is as follows

 public int minDistance(String word1, String word2) {
        
        // write your code here
        if(null == word1 || null == word2){
           return 0;
        }
        
        int[][] arr=new int[word1.length()+1][word2.length()+1];
        for(int i=0; i<=word1.length(); i++){ arr[i][0]=i; }for(int j=1; j<=word2.length(); j++){ arr[0][j]=j; }for(int i=1; i<=word1.length(); i++){for(int j=1; j<=word2.length(); j++){if(word1.charAt(i-1)==word2.charAt(j-1)){
                   arr[i][j]=Math.min(Math.min(arr[i][j-1]+1,arr[i-1][j]+1),arr[i-1][j-1]); 
                }else{ arr[i][j]=Math.min(Math.min(arr[i][j-1]+1,arr[i-1][j]+1),arr[i-1][j-1]+1); }}}return arr[word1.length()][word2.length()];
    }
Copy the code