0

我正在尝试编写一个程序来计算英语中任意两个单词之间的编辑距离。编辑距离定义为通过一次仅更改一个字母从一个单词转到另一个单词所需的最小步数，其中每个中间单词都包含在一些标准的英语单词列表中。我将提示用户输入两个词。例如，如果用户输入：“trail”和“crawl”，我希望输出为：

First word:  trail
Last word: crawl
The edit distance is 2 with the following chain: trail -> trawl -> crawl

（所以它也包括路径）

import java.util.Scanner;
import java.io.*;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;

public class EditDistance {
 public static void main (String[] args) {
    try {
        inputDictionary();
    }
    catch (FileNotFoundException e) {
    System.out.println("Error: FileNotFoundException");
    }
    promptUser();
}

static ArrayList<String> dictionary;

    //input dictionary
public static void inputDictionary() throws FileNotFoundException {
    dictionary = new ArrayList<String>();
    Scanner scan = new Scanner(new File ("dict.txt"));
    while (scan.hasNext()) {
        String word = scan.next();
        dictionary.add(word);
    }
    scan.close();
}

public static HashSet<String> changeOneLetter(String Word) {
    HashSet<String> newWords = new HashSet<String>();
    char alphabet[] = "abcdefghijklmnopqrstuvwxyz".toCharArray();
        //take each letter and change it to a different letter
        for (int i = 0; i < Word.length(); i++) { //cycles through each letter of the word
            char wordArray[] = Word.toCharArray();
            for (int j = 0; j < 26; j++) { //swaps in each letter of the alphabet
                wordArray[i] = alphabet[j];
                //check if it's not the same as previous word
                String newWord = new String(wordArray);
                if (!newWord.equals(Word)) {
                    // if it's in the dictionary add the word to the set
                    for (String word1: dictionary) {
                        if (newWord.equals(word1)) {
                            newWords.add(newWord);
                        }
                    }
                }
            }
        }
    return newWords;
}

static Map<String, Set<String>> eachWordChange;
static String firstWord;
static String secondWord;

    //prompts the user for two words
public static void promptUser() {
    System.out.println("Enter the first word: ");
    Scanner scan = new Scanner(System.in);
    firstWord = scan.next();
    for (String word1: dictionary) {
        if (firstWord.equals(word1)) {
            System.out.println("Enter the second word: ");
            secondWord = scan.next();
            for (String word2: dictionary) {
                if (secondWord.equals(word2)) {
                    calculateEdits();
                }
            }
        }
    }
    scan.close();
}

   //this is where I'm having trouble
public static void calculateEdits() {
    String oldWord = secondWord;
    Map <String, String> findPath = new HashMap<String, String>();
    HashSet<String> oneLevel = changeOneLetter(oldWord);
    System.out.println("This is the first level: " + oneLevel);
    for (String word: oneLevel) {
        if (!firstWord.equals(word)) {

            findPath.put(word, secondWord);
            System.out.println("Next Levels: " + changeOneLetter(word));
    }
    System.out.println("Path of first level: " + findPath);
}

}

现在我只有 println's 来向我展示发生了什么，所以现在它正在向我展示：

This is the first level: [trawl, brawl, drawl]
Next Levels: [brawl, trail, crawl, drawl]
Next Levels: [trawl, crawl, drawl]
Next Levels: [trawl, brawl, crawl, drawn]
Path of first level: {trawl=crawl, brawl=crawl, drawl=crawl}

现在我有第一级，并且可以从每个第一级生成第二级，但我希望能够存储下一个级别，然后检查第一个单词（=trail）是否出现在那里，如果它在第一个单词出现之前，我不必创建地图并重做该过程。

4

0 回答 0