第一個單詞匹配後的退出遞歸

Question

此函數設計爲拼寫錯誤的單詞並對其進行排列，檢查每個完整排列與單詞列表直到找到匹配。

一旦找到匹配，該函數就意味着終止並立即返回匹配的單詞，而無需進一步進行置換。

在當前狀態下，函數可以工作，但是它繼續進行排列並找到匹配，直到所有排列完成。

函數find（）可能被認爲是一個黑盒子，如果該單詞與dcnV向量中的單詞相匹配，則返回true;如果不匹配，則返回false。此功能正常工作。

dcnV：包含字典中單詞列表的字符串向量。

pos：整數由遞歸算法使用。

p []：解法數組。

used []：跟蹤在當前排列中使用哪些索引的數組。

word：從調用函數傳入此函數的詞（來自文本文件）。

string permute (vector <string> dcnV , int pos , int p [] , 
    int used [] , string & word) 
{ 
    string tgt = word; //sets tgt to have the same size as word 

    unsigned int n = word.size(); //determines for loop range 
    unsigned int i = 0; //iterator 

    /* base case: when the end of the array is reached, 
    * map tgt to word using p array indexes 
    * search dictionary vector dcnV for matching word 
    * if found, return tgt 
    */ 
    if (pos == n && p [0] == 0 && p [n - 1] == n - 1) 
    { 
     for (i = 0; i < n; i++) 
     { 
      tgt [i] = word [p[i]]; 
     } 

     if (find (dcnV , tgt)) 
     { 
      cout << "\n Found matching word: " << tgt; 
      return tgt; 
     } 
    } 

    // recursive permutation algorithm. this is functioning correctly 
    for (i = 0; i < n; i++) 
    { 
     if (used [i] == 0) 
     { 
      p [pos] = i; 
      used [i] = 1; 
      permute (dcnV , pos + 1 , p , used , word); 
      used [i] = 0; 
     } 
    } 

    // if end of fn is reached without match, return tgt with '*' appended in 
    // front 
    return "*" + word; 
} 

試圖解決方案不起作用：

使用靜態矢量持有匹配的話，那麼只返回該向量的第一個元素。

設置一個標誌，當一個單詞被發現，並添加一個邏輯檢查在功能的開始，立即返回，如果標誌設置。

可能不會使用setjmp，longjmp，exit，break和exceptions。

Answer 1

請使用-std=c++11編譯，或者只是複製置換功能

#include <iostream> 
#include <vector> 
#include <string> 
#include <algorithm> 
using namespace std; 

bool find(vector<string> &vs, string &s) { 
    // or use std::find, but you provide a wrong parameters 
    for (int i = 0; i < vs.size(); i++) { 
    if (vs[i] == s) return true; 
    } 
    return false; 
} 

string permute (vector <string>& dcnV , int pos , int p [] , 
       int used [] , string & word) 
{ 
    string tgt = word; //sets tgt to have the same size as word 

    unsigned int n = word.size(); //determines for loop range 
    unsigned int i = 0; //iterator 

    /* base case: when the end of the array is reached, 
    * map tgt to word using p array indexes 
    * search dictionary vector dcnV for matching word 
    * if found, return tgt 
    */ 
    // if (pos == n && p [0] == 0 && p [n - 1] == n - 1) 
    // { 
    // when pos == n, we should terminate this recurve immediately 
    if (n == pos) { 
    for (i = 0; i < n; i++) 
    { 
     tgt [i] = word [p[i]]; 
    } 

    if (find (dcnV , tgt)) 
    { 
     cout << "\n Found matching word: " << tgt << endl; 
     return tgt; 
    } else { 
     return ""; 
    } 
    } 

    // recursive permutation algorithm. this is functioning correctly 
    for (i = 0; i < n; i++) 
    { 
    if (used [i] == 0) 
    { 
     p [pos] = i; 
     used [i] = 1; 
     string t = permute (dcnV , pos + 1 , p , used , word); 
     // we have found a solution, return now 
     if (t != "") return t; 
     used [i] = 0; 
    } 
    } 

    // if end of fn is reached without match, return tgt with '*' appended in 
    // front 
    // suppose you do not search an empty string... 
    return ""; 
} 


int main(int argc, char ** argv) { 
    vector<string> vs = {"abcd", "asdf", "qqwer", "werq"}; 
    string word = "reqw"; 
    string word_nonexist = "asdsaf"; 

    int p[100] = {0}; 
    int used[100] = {0}; 

    string t1 = permute(vs, 0, p, used, word); 
    string t2 = permute(vs, 0, p, used, word_nonexist); 
    // cout << t <<endl; 

    return 0; 
}