Câu hỏi này đã được hỏi trong một cuộc phỏng vấn

Giả sử bạn có một từ điển gồm các từ: (sử dụng nếu bạn có /usr/share/dict/words).

Cho một từ (ví dụ: cricket), hãy cung cấp cho tôi tất cả các từ trong từ điển có thể đạt được bằng cách thực hiện n thao tác Trong đó một thao tác là một trong:
Phép cộng
Thay thế
Xóa

Ví dụ: nếu chỉ cho phép 1 thao tác, hãy tìm tất cả các từ có thể được tạo thành từ "cricket".

{'word': 'clicket', 'op': ['replace']}{'word': 'crickey', 'op': ['replace']}{'word': 'crickety', 'op' : ['bổ sung']}, v.v.

Tôi đang in ở định dạng của riêng mình, nhưng bạn hiểu ý chính.

Đây là những gì tôi đã thử

1. Tính toán tất cả các thứ tự danh sách có thể dựa trên số lượng hoạt động.
2. Sau đó lặp qua danh sách và áp dụng từng từ một và lưu trữ lần xuất hiện của các từ trong từ điển.

Đây là một giải pháp vũ phu. Tôi muốn biết liệu có giải pháp hiệu quả nào không. Sau đây là mã để bẻ khóa bằng lực lượng vũ phu

import java.io.BufferedReader;
nhập java.io.FileNotFoundException;
nhập java.io.FileReader;
import java.io.IOException;
nhập java.util.ArrayList;
nhập java.util.HashMap;
nhập java.util.Iterator;
nhập java.util.List;
nhập java.util.Map;


lớp công khai Tương tựWordDistance {

    Từ điển Map = new HashMap();
    int THÊM = -1;
    int THAY THẾ = 0;
    int XÓA = 1;

    /**
     * @param lập luận
     * @throwsIOException 
     */
    public static void main(String[] args) ném IOException {

        SameWordDistance swd = new SameWordDistance();
        swd.readDictionary();
        //swd.findSimilar("cricket", 1);
        swd.findSimilar("hạnh phúc", 3);
    }

    public void findSimilar(String word,int num) {
        int couldOperations = (int) Math.pow(3, num);
        Các phép toán số nguyên[][] = Số nguyên mới[possibleOperations][num];
        buildOperationsArray(num,ableOperations, Operations);
        Danh sách l = new ArrayList();
        l.add(từ);
        Map sols = new HashMap();

        for(int i=0;i<>
            applyOperation(hoạt động[i],l,sols);

        Iterator itr = sols.keySet().iterator();
        while(itr.hasNext()) {
            Chuỗi n = itr.next();
            printSolution(sols.get(n), n);
        }
    }


    void void applyOperation(Integer[] Operation,List word,Map sols) {
        Danh sách  khả năng = từ;
         for(int i=0;i
            if(hoạt động[i] == THÊM) {
                Danh sách temp = new ArrayList();
                for(int j =0;j
                   temp.addAll(applyAdditionOperation(possiblities.get(j)));
                   //System.out.println(temp.size());
                }
                khả năng = tạm thời;
            } 
            if(hoạt động[i] == THAY THẾ) {
                Danh sách temp = new ArrayList();
                for(int j =0;j
                    temp.addAll(applyReplace(possiblities.get(j)));
                    //System.out.println(temp.size());
                 }
                khả năng = tạm thời;
            }
            if(hoạt động[i] == XÓA) {
                Danh sách temp = new ArrayList();
                for(int j =0;j
                    temp.addAll(applyDeletion(possiblities.get(j)));
                 }
                khả năng = tạm thời;
            }
        }

        for(int i=0;i
            Chuỗi w = khả năng.get(i);
            if(dictionary.containsKey(w)) {
                sosol.put(w, thao tác);
            }
        }

    }

    protected void printSolution(Hoạt động Integer[], Chuỗi w) {
        System.out.print(w+"\t" );
        for(int j=0;j
            System.out.print(printOperation(Operation[j])+"\t");
        }
        System.out.println();
    }

    Chuỗi riêng tư printOperation(Số nguyên) {
        if(số nguyên == THÊM) {
            trả về "Bổ sung";
        } if(số nguyên == THAY THẾ) {
            trả về "Thay thế";
        } khác {
            trả về "Xóa";
        }
    }

    Danh sách riêng tư applyAdditionOperation(String word) {
        char[] khả năng = {'a','b','c','d','e','f','g','h','i','j','k', 'l','m','n','o','p','q','r','s','t','u','v','w','y ','z'};
        Danh sách có thểWords = new ArrayList();
        for(int i=0;i
            for(int j=0;j
                Chuỗi temp = InsertAt(word,j,possiblities[i]);
                có thểWords.add(temp);
            }
        }
        trả lại các từ có thể;
    }

    Danh sách riêng tư applyDeletion(String word) {
        Danh sách có thểWord = new ArrayList();
        for(int i=0;i
            Tiền tố chuỗi = word.substring(0,i);
            Hậu tố chuỗi = word.substring(i+1,word.length());
            Chuỗi tenp = tiền tố+hậu tố;
            có thểWord.add(tenp);
        }
        trả lại từ có thể;
    }

    Danh sách riêng tư applyReplace(String word) {
        char[] khả năng = {'a','b','c','d','e','f','g','h','i','j','k', 'l','m','n','o','p','q','r','s','t','u','v','w','y ','z'};
        Danh sách có thểWord = new ArrayList();
        for(int i=0;i
            for(int j=0;j
                Chuỗi temp = word.substring(0,j)+possiblities[i]+word.substring(j+1,word.length());
                if(temp.length()!=word.length()) 
                    System.out.println("######################");
                có thểWord.add(temp);
            }
        }
        trả lại từ có thể;
    }

    Chuỗi riêng chènAt(Chuỗi word, int j, char c) {
        Tiền tố chuỗi = word.substring(0,j);
        Hậu tố chuỗi = word.substring(j+1,word.length());
        Chuỗi ret = tiền tố+c+hậu tố;
        return ret;
    }

    protected void buildOperationsArray(int num, int couldOperations,
            Phép toán số nguyên[][]) {
        for(int i=0;i<>
            for(int j=0;j
                fillPossiblities(num, actions, ADDTION, i, j); // 3 hàng
                if(i+3
                    fillPosossiblities(num, actions, REPLACE, i+3, j); // 3 hàng
                if(i+6 < có thểHoạt động)
                fillPosossiblities(num, actions, DELETION, i+6, j); // 3 hàng
            }
        }
       /* System.out.println(Operations.length);
        for(int i=0;i
            for(int j=0;j
                System.out.print(hoạt động[i][j]+"\t");
            }
            System.out.println();
        }*/
    }


    /**
     * Mỗi lần phương thức này được gọi nó sẽ điền vào tất cả các cột của hàng được truyền
     * với 1 giá trị mặc định và điền vào 2 hàng tiếp theo với khả năng hoán vị của giá trị đó
     *cột
     * @param num
     * Hoạt động @param
     * @param chắc chắn
     * @param curRow
     */
    protected void fillPossiblities(int num, Integer[][] actions,int def,int curRow,int curColumn) {
        for(int i=0;i
            hoạt động [curRow] [i] = def;
        }
        for(int i=0;i
            if(i!=curColumn)
                hoạt động [curRow+1] [i] = def;
        }
        hoạt động [curRow+1] [curColumn] = getNext(def);
        int def1 = getNext(def);
        for(int i=0;i
            if(i!=curColumn)
                hoạt động [curRow+2] [i] = def;
        }
        hoạt động [curRow+2] [curColumn] = getNext(def1);
    }

    int riêng tư getNext(int def) {
        nếu(def == -1) {
            trả về THAY THẾ;
        }
        nếu(def == 0) {
            trả về XÓA;
        } khác {
            trả lại THÊM;
        }
    }

    public void readDictionary() ném IOException {

        BufferedReader in = new BufferedReader(new FileReader("C:\\Documents\\Downloads\\words"));

        trong khi (in.ready()) {
          Chuỗi s = in.readLine();
          từ điển.put(s, true);
        }
        in.close();
    }

}

câu trả lời hay nhất

Đối với mỗi từ trong từ điển
   d = khoảng cách chỉnh sửa tối thiểu (từ đã cho, từ)
   nếu d <= n
      in (chữ)

Khoảng cách chỉnh sửa tối thiểu có thể được giải quyết bằng thuật toán lập trình động nổi tiếng với độ phức tạp là O(n*m) 其中 n Và m là độ dài của hai từ.

Bài viết Wikipedia có cách triển khai:http://en.wikipedia.org/wiki/Levenshtein_distance

Về java - [Phỏng vấn] Tính toán khoảng cách từ tương tự, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/19904285/