Thuật toán chuyển đổi một từ sang người khác qua lời hợp lệ

Question

Tôi đã xem qua sự thay đổi này của edit-distance vấn đề:

Thiết kế một thuật toán mà biến một văn bản nguồn để một từ mục tiêu. ví dụ: từ đầu đến đuôi, trong mỗi bước, bạn chỉ có thể thay thế một ký tự và từ phải hợp lệ. Bạn sẽ được cung cấp một từ điển.

Nó rõ ràng là một biến thể của vấn đề edit distance, nhưng trong khoảng cách chỉnh sửa tôi không quan tâm về việc từ đó có hợp lệ hay không. Vậy làm cách nào để thêm yêu cầu này để chỉnh sửa khoảng cách.

Answer 1

Điều này có thể được mô hình hóa dưới dạng vấn đề đồ thị. Bạn có thể nghĩ các từ như các nút của biểu đồ và hai nút được kết nối nếu và chỉ khi chúng có cùng chiều dài và khác nhau trong một char.

Bạn có thể preprocess điển và tạo biểu đồ này, nên hình như:

stack jack 
    |  | 
    |  | 
    smack back -- pack -- pick 

Sau đó bạn có thể có một ánh xạ từ từ vào nút đại diện cho văn bản, cho điều này bạn có thể sử dụng một bảng băm, chiều cao cân bằng BST ...

Khi bạn đã có bản đồ ở trên, tất cả những gì bạn phải làm là xem liệu có tồn tại đường dẫn giữa hai nút đồ thị, có thể dễ dàng thực hiện bằng BFS hay DFS.

Vì vậy, bạn có thể tóm tắt các thuật toán như:

preprocess the dictionary and create the graph. 
Given the two inputs words w1 and w2 
if length(w1) != length(w2) 
Not possible to convert 
else 
n1 = get_node(w1) 
n2 = get_node(w2) 

if(path_exists(n1,n2)) 
    Possible and nodes in the path represent intermediary words 
else 
    Not possible 

Answer 2

Tôi không nghĩ đây là khoảng cách chỉnh sửa.

Tôi nghĩ điều này có thể được thực hiện bằng biểu đồ. Chỉ cần tạo biểu đồ từ từ điển của bạn và cố điều hướng bằng thuật toán truyền tải đồ thị yêu thích của bạn đến đích.

Answer 3

phương pháp đồ thị codaddict là hợp lệ, mặc dù (n^2) thời gian cần O để xây dựng mỗi đồ thị, trong đó n là số từ của một định chiều dài. Nếu đó là một vấn đề, bạn có thể xây dựng một bk-tree hiệu quả hơn nhiều, giúp bạn có thể tìm thấy tất cả các từ có khoảng cách chỉnh sửa đã cho (trong trường hợp này là 1) của từ mục tiêu.

Answer 4

Đây rõ ràng là một vấn đề hoán vị. Sử dụng biểu đồ quá mức cần thiết. Báo cáo sự cố thiếu một hạn chế quan trọng; mà bạn chỉ có thể thay đổi từng vị trí một lần. Điều này sau đó làm cho nó ngầm rằng giải pháp là trong vòng 4 bước. Bây giờ tất cả những gì cần phải được quyết định là chuỗi các hoạt động thay thế:

Operation1 = thay đổi "H" để "T"
Operation2 = thay đổi "E" để "A"
Operation3 = thay đổi "A" để "tôi"
Operation4 = thay đổi "D để 'L'

các giải pháp, chuỗi các hoạt động, một số hoán vị của chuỗi '1234', trong đó mỗi chữ số đại diện cho vị trí của các nhân vật được thay thế. ví dụ "3124" chỉ ra rằng đầu tiên chúng ta áp dụng operation3, sau đó operation1, sau đó operation2, sau đó hoạt động 4. Ở mỗi bước, nếu kết quả từ không có trong từ điển, hãy bỏ qua đến hoán vị tiếp theo. ode ai?

Answer 5

Tạo biểu đồ với mỗi nút đại diện cho từ trong từ điển. Thêm một cạnh giữa hai nút từ, nếu từ tương ứng của chúng ở khoảng cách chỉnh sửa là 1.Sau đó, số lượng tối thiểu các phép biến đổi được yêu cầu sẽ có chiều dài đường đi ngắn nhất giữa nút nguồn và nút đích.

Answer 6

Đây là mã C# để giải quyết vấn đề bằng BFS:

//use a hash set for a fast check if a word is already in the dictionary 
    static HashSet<string> Dictionary = new HashSet<string>(); 
    //dictionary used to find the parent in every node in the graph and to avoid traversing an already traversed node 
    static Dictionary<string, string> parents = new Dictionary<string, string>(); 

    public static List<string> FindPath(List<string> input, string start, string end) 
    { 
     char[] allcharacters = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; 

     foreach (string s in input) 
      Dictionary.Add(s); 
     List<string> currentFrontier = new List<string>(); 
     List<string> nextFrontier = new List<string>(); 
     currentFrontier.Add(start); 
     while (currentFrontier.Count > 0) 
     { 
      foreach (string s in currentFrontier) 
      { 
       for (int i = 0; i < s.Length; i++) 
       { 
        foreach (char c in allcharacters) 
        { 
         StringBuilder newWordBuilder = new StringBuilder(s); 
         newWordBuilder[i] = c; 
         string newWord = newWordBuilder.ToString(); 
         if (Dictionary.Contains(newWord)) 
         { 
          //avoid traversing a previously traversed node 
          if (!parents.Keys.Contains(newWord)) 
          { 
           parents.Add(newWord.ToString(), s); 
           nextFrontier.Add(newWord); 
          } 

         } 
         if (newWord.ToString() == end) 
         { 
          return ExtractPath(start, end); 

         } 
        } 
       } 
      } 
      currentFrontier.Clear(); 
      currentFrontier.Concat(nextFrontier); 
      nextFrontier.Clear(); 
     } 
     throw new ArgumentException("The given dictionary cannot be used to get a path from start to end"); 
    } 

    private static List<string> ExtractPath(string start,string end) 
    { 
     List<string> path = new List<string>(); 
     string current = end; 
     path.Add(end); 
     while (current != start) 
     { 
      current = parents[current]; 
      path.Add(current); 
     } 
     path.Reverse(); 
     return path; 
    } 

Answer 7

Bạn chỉ có thể sử dụng đệ quy back-theo dõi nhưng điều này còn xa mới là giải pháp tối ưu nhất.

# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only 
# one letter at a time. The new word you get in each step must be in the 
# dictionary. 

# def transform(english_words, start, end): 

# transform(english_words, 'damp', 'like') 
# ['damp', 'lamp', 'limp', 'lime', 'like'] 
# ['damp', 'camp', 'came', 'lame', 'lime', 'like'] 


def is_diff_one(str1, str2): 
    if len(str1) != len(str2): 
     return False 

    count = 0 
    for i in range(0, len(str1)): 
     if str1[i] != str2[i]: 
      count = count + 1 

    if count == 1: 
     return True 

    return False 


potential_ans = [] 


def transform(english_words, start, end, count): 
    global potential_ans 
    if count == 0: 
     count = count + 1 
     potential_ans = [start] 

    if start == end: 
     print potential_ans 
     return potential_ans 

    for w in english_words: 
     if is_diff_one(w, start) and w not in potential_ans: 
      potential_ans.append(w) 
      transform(english_words, w, end, count) 
      potential_ans[:-1] 

    return None 


english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like']) 
transform(english_words, 'damp', 'lame', 0) 

Answer 8

Tôi không nghĩ chúng tôi cần đồ thị hoặc một số cấu trúc dữ liệu phức tạp khác. Ý tưởng của tôi là tải từ điển dưới dạng HashSet và sử dụng phương pháp để tìm hiểu xem từ đó có tồn tại trong từ điển hay không.

Xin vui lòng, kiểm tra này giả để xem ý tưởng của tôi:

Two words are given: START and STOP. 
//List is our "way" from words START to STOP, so, we add the original word to it first. 
    list.add(START); 
//Finish to change the word when START equals STOP. 
    while(!START.equals(STOP)) 
//Change each letter at START to the letter to STOP one by one and check if such word exists. 
    for (int i = 0, i<STOP.length, i++){ 
     char temp = START[i]; 
     START[i] = STOP[i]; 
//If the word exists add a new word to the list of results. 
//And change another letter in the new word with the next pass of the loop. 
     if dictionary.contains(START) 
      list.add(START) 
//If the word doesn't exist, leave it like it was and try to change another letter with the next pass of the loop. 
     else START[i] = temp;} 
    return list; 

Theo tôi được biết mã của tôi nên làm việc như thế:

Input: ẩm ướt, LIKE

Output: DAMP, LAMP, LIMP, LIME, LIKE

Input: BACK, PICK

Output: BACK, PACK, PICK