javascript - 尝试使用 JavaScript 中的变音符号使递归排列函数

Question

我设法编写了一个简单的函数，该函数接受一个输入字符串，并将每个字符与一个字典对象进行比较，该字典对象包含与其非变音符号配对的变音符号（重音）字符，然后尝试为每个排列创建一个新字符串。

但是，它只是半功能性的。当我输入字符串'hello world'时，输出是：

["hèllo world", "héllo world", "hêllo world", "hëllo world", "hēllo world", 
"hėllo world", "hęllo world", "hellô world", "hellö world", "hellò world", 
"helló world", "hellō world", "hellõ world", "hello wôrld", "hello wörld", 
"hello wòrld", "hello wórld", "hello wōrld", "hello wõrld"]

或者如果我输入“一些字符串”，那么输出是：

["śome string", "šome string", "sôme string", "söme string", "sòme string", 
"sóme string", "sōme string", "sõme string", "somè string", "somé string", 
"somê string", "somë string", "somē string", "somė string", "somę string", 
"some śtring", "some štring", "some strîng", "some strïng", "some stríng", 
"some strīng", "some strįng", "some strìng", "some striñg", "some strińg"]

然而，它所做的只是遍历每个字符并替换一次值，然后移动到下一个字符。

如何为每个数组项再次迭代以找到它们的所有可能组合？而不是移动到下一个字符并留下与原始输入字符串相同的字符。我需要它有每一个排列。

我整晚都在努力解决这个问题，尽管我取得了一些进展，但我仍然陷入困境。我试图创建一个从自身内部调用自身的递归函数，但这只是让我的浏览器崩溃。

任何帮助都会很棒:)

这是我写的代码：

function jig(inputStr) {
  const accents = {
    a: ["à", "á", "â", "ä", "ã", "å", "ā"],
    c: ["ç", "ć", "č"],
    e: ["è", "é", "ê", "ë", "ē", "ė", "ę"],
    i: ["î", "ï", "í", "ī", "į", "ì"],
    n: ["ñ", "ń"],
    o: ["ô", "ö", "ò", "ó", "ō", "õ"],
    s: ["ś", "š"],
    u: ["û", "ü", "ù", "ú", "ū"],
    y: ["ÿ"],
    z: ["ž", "ź", "ż"]
  };

  function hasAccents(char) {
    return /[aceinosuyz]/.test(char);
  }

  var results = [];

  for (var i = 0; i < inputStr.length; i++) {
    var currentChar = inputStr.substr(i, 1);
    // console.log(currentChar);
    if (hasAccents(currentChar)) {
      // console.log(accents[currentChar]);

      for (var y = 0; y < accents[currentChar].length; y++) {
        var tempArray = inputStr.split("");

        tempArray[i] = accents[currentChar][y];
        results.push(tempArray.join(""));
        //jig(tempArray.join(""));
      }
    }
  }

  return results;
}

标签： javascriptrecursionpermutationsubstrbacktracking

Answer 1

这是一个构建每个字符串的方法。当遇到重音候选字符时，我们将字符串的每个版本推送到堆栈，直到该字符。

JavaScript 代码：

function f(s){
  const accents = {
    a: ["à", "á", "â", "ä", "ã", "å", "ā"],
    c: ["ç", "ć", "č"],
    e: ["è", "é", "ê", "ë", "ē", "ė", "ę"],
    i: ["î", "ï", "í", "ī", "į", "ì"],
    n: ["ñ", "ń"],
    o: ["ô", "ö", "ò", "ó", "ō", "õ"],
    s: ["ś", "š"],
    u: ["û", "ü", "ù", "ú", "ū"],
    y: ["ÿ"],
    z: ["ž", "ź", "ż"]
  };
  
  var result = [];
  
  var stack = [['', 0]];
  
  while (stack.length){
    let [str, i] = stack.pop();
    
    if (i == s.length){
      result.push(str);
      continue;
    }
    
    if (accents[s[i]]){
      for (let j=0; j<accents[s[i]].length; j++)
        stack.push([str + accents[s[i]][j], i + 1]);
    }

    stack.push([str + s[i], i + 1]);
  }
  
  return result;
}

console.log(f('hello'));