Now there are two strings, mother and monster. To change mother into monster, each operation can only modify one letter, delete one letter, and add one letter. There are many editing paths to change monther into monster. We need Find the shortest edit path, because the similarity of these two strings is determined by the minimum edit distance.
Let’s demonstrate the search process:
m o t h e r :
1. m o n h e r ( t is modified to n )
1. m o n s e r (h is changed to s)
1. m o n s t r (e is modified to t)
1. m o n s t e (r is modified to e)
1. m o n s t e r (add r, end)
2. m o n s t r (add r)
1. m o n s t e (r is modified to e)
1. m o n s t e r (add r, end)
2. m o n s t r r (add r)
1. m o n s t e r (r is changed to e, end)
2. m o n s e e ( r is changed to e )
1. m o n s t e (e is modified to t)
1. m o n s t e r (add r, end)
2. m o n s e e r (add r)
1. todo
2.
3.
3. m o n s e r r (add r)
2. m o n h t r (e is modified to t)
3. m o n h e r ( r is changed to e )
4. m o n h e r r (add r)
2. m o t s e r (h is changed to s)
1. m o n s e r (t is modified to n)
2. m o t s t r (e is modified to t)
3. m o t s e e ( r is changed to e )
4. m o t s e r r (add r)
3. m o t h t r (e is changed to t)
1. m o n h t r (t is modified to n)
2. m o t s t r (h is changed to s)
3. m o t h t e ( r is changed to e )
4. m o t h t r r (add r)
4. m o t h e e (replace r with e)
5. m o t h e r r (add r)
NodeVO.java：
import lombok.Getter;
import lombok.Setter;
import java.io.PipedReader;
import java.io.Serializable;
import java.util.List;
@Getter
@Setter
public class NodeVO implements Serializable {
private String str;
private NodeVO parent;
private List<NodeVO> children;
}
StringEditDistanceTest.java：
import com.alibaba.fastjson.JSONObject;
import java.util.*;
public class StringEditDistanceTest {
/*
// First align the two letters according to the head,
// Each time you can add (choose a position to add the missing letters), delete (choose a position to delete the extra letters), change (choose a letter that is different from the corresponding position of the target string to replace)
m o t h e r
m o n s t e r
m o t h e r :
1. m o n h e r ( t is modified to n )
1. m o n s e r (h is changed to s)
1. m o n s t r (e is modified to t)
1. m o n s t e (r is modified to e)
1. m o n s t e r (add r, end)
2. m o n s t r (add r)
1. m o n s t e (r is modified to e)
1. m o n s t e r (add r, end)
2. m o n s t r r (add r)
1. m o n s t e r (r is changed to e, end)
2. m o n s e e ( r is changed to e )
1. m o n s t e (e is modified to t)
1. m o n s t e r (add r, end)
2. m o n s e e r (add r)
1. todo
2.
3.
3. m o n s e r r (add r)
2. m o n h t r (e is modified to t)
3. m o n h e r ( r is changed to e )
4. m o n h e r r (add r)
2. m o t s e r (h is changed to s)
1. m o n s e r (t is modified to n)
2. m o t s t r (e is modified to t)
3. m o t s e e ( r is changed to e )
4. m o t s e r r (add r)
3. m o t h t r (e is changed to t)
1. m o n h t r (t is modified to n)
2. m o t s t r (h is changed to s)
3. m o t h t e ( r is changed to e )
4. m o t h t r r (add r)
4. m o t h e e (replace r with e)
5. m o t h e r r (add r)
*/
public static void main(String[] args) {
String str_src = "hello";
String str_target = "halllo";
// searchShortestEditDistance( str_src,str_target );
List<Character> letters = getLettersThatStr1Lack(str_src, str_target);
System.out.println( JSONObject.toJSONString( letters ) );
}
private static List<Character> string2Letters( String str ){
int length = str.length();
List<Character> letters = new ArrayList<>();
for(int i = 0;i < length;i + + ){
letters.add( str.charAt(i) );
}
return letters;
}
/**
* Returns the missing letter set of srcStr
* @param str1
* @param str2
* @return
*/
private static List<Character> getLettersThatStr1Lack( String str1,String str2 ){
List<Character> letters1 = string2Letters(str1);
List<Character> letters2 = string2Letters(str2);
// hello halllooo
ListIterator<Character> iterator = letters2.listIterator();
while (iterator.hasNext() ){
Character letter = iterator.next();
if( letters1.contains( letter ) ){
letters1.remove( letter );
iterator.remove();
}
}
return letters2;
}
/**
* @param beginString
* @param endString
*/
private static void searchShortestEditDistance(String beginString, String endString) {
List<NodeVO> nodes_currLevel = new ArrayList<>();
NodeVO node_begin = new NodeVO();
node_begin.setStr(beginString);
nodes_currLevel.add( node_begin );
List<NodeVO> nodes_nextLevel = new ArrayList<>();
boolean finish = false;
int treeDeep = 0;
while( true ){
if( nodes_currLevel.size() == 0 ){
break;
}
// First align the two letters according to the head (todo, for example, why do we need to align the head here? Is it best to choose a position that can have the largest intersection after alignment?)
// Each time you can add (choose a position to add the missing letter), delete (choose a position to delete the extra letters), change (choose a letter to replace the corresponding position of the target string)
// m o t h e r
// m o n s t e r
treeDeep++;
for(NodeVO node:nodes_currLevel){
String currString = node.getStr();
if( currString.equals( endString ) ){
// Has been converted into the target string
finish = true;
break;
}
// compared to the target string, check the missing character set and excess character set of the current string,
// todo For missing characters, try to add them as much as possible
// todo For the extra characters, try to delete or modify them (ps: modify them to the missing characters. If there are no missing characters, you can only delete them)
// Missing character set
List<Character> letters_lack = getLettersThatStr1Lack(currString, endString);
//extra character set
List<Character> letters_redundant = getLettersThatStr1Lack(endString, currString);
if( letters_lack == null || letters_lack.size() == 0 ){
if( letters_redundant == null || letters_redundant.size() == 0 ){
// There is no shortage of characters, nor too many characters. This situation is impossible, because there is neither shortage nor too many characters, which means they are equal, and there will be a break in front of it.
}else{
// todo has no shortage of characters, only more characters. It traverses the collection of extra characters and performs deletion operations.
// First align the two letters according to the head (todo, for example, why do we need to align the head here? Is it best to choose a position that can have the largest intersection after alignment?)
// Each time you can add (choose a position to add the missing letter), delete (choose a position to delete the extra letters), change (choose a letter to replace the corresponding position of the target string)
// m o t h e r
// m o n s t e r
for(Character letter_redundant:letters_redundant){
NodeVO node_ = new NodeVO();
// todo will delete the experience string obtained later from currString
node_.setStr(null);
node_.setParent( node );
}
}
}else {
if( letters_redundant == null || letters_redundant.size() == 0 ){
// todo is only missing characters, not many characters
}else{
// todo
// todo means missing characters or too many characters
}
}
}
if(finish){
break;
}
nodes_currLevel = nodes_nextLevel;
nodes_nextLevel = new ArrayList<>();
}
}
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57266 people are learning the system