数组搜索和切片

Question

给定仅包含数字的字符串 nums 和数字数组 predefinedNumbers，我必须基于 nums 构造一个新字符串，但冒号之间的每个数字都有成为来自预定义数字和 return 所有可能性的有效数字。

示例输入：

nums = "143163421154143"
predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"]

期望的输出：

[ ":143:1634:21154:143:", ":143:163421154:143:", ":143:1634:21154143:" ]

到目前为止，我尝试了这段代码，但它不是我需要的结果，我一直在尝试了解如何递归地检查它：

let nums = "143163421154143";
predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"];


let newArray=[];
function makeNumSentences (nums, predefinedNumbers) {
    predefinedNumbers.map(item => {
        if (nums.includes(item)) {
            newArray.push(item)
        }
    })
    
    console.log(newArray.join(':'));
        };
        
        
makeNumSentences("143163421154143",["21154", "143", "21154143", "1634", "163421154"])

非常感谢任何提示。

Answer 1

请注意，如果 nums 不仅仅由 predefinedNumbers 组成，循环将永远不会结束。

const nums = "143163421154143";
const predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"];
const result = [];

function makeNumSentences(nums) {
  check([], nums);
  console.log(result);
};

function check(array, nums) {
  predefinedNumbers.forEach(e => {
    if (nums.startsWith(e)) {
      const newArray = array.concat(e);
      const newNums = nums.slice(e.length);
      if (newNums) { check(newArray, newNums); }
      else { result.push(newArray.join(':')); }
    }
  });
}
        
        
makeNumSentences(nums);

Answer 2

首先，请阅读How do I ask and answer homework questions?。

虽然已经有一个可接受的答案，但我将只展示另一种方法。元素是数字这一事实是没有意义的。同样的技术适用于任何字符串。（有数学技巧可以找到正确的值，但它们会很快溢出正常数字，而且由于无论如何输出都需要是一个字符串，所以似乎没有必要去追求它们。）

递归地考虑这个问题，我们可以把它分成两部分。我的哪些预定义值出现在目标字符串的开头？对于其中的每一个，我如何对字符串的其余部分执行相同的操作？递归需要一个基本情况，我们可以说如果目标字符串为空，那么我们可以 return 一个空字符串。

我们可以这样实现：

const make = (target, sources) =>
  target .length == 0
    ? [[]]
    : sources .filter (s => target .startsWith (s)) 
              .flatMap (s => make (target .slice (s .length), sources) .map (r => [s, ...r]))

const makeNumSentences = (target, parts) => 
  make (target, parts) .map (r => `:${r.join(':')}:`)


const nums = "143163421154143"
const predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"]

console .log (makeNumSentences (nums, predefinedNumbers))

请注意主要递归函数的细分，其中 return 是来自我们源 ([["143", "1634", "21154", "143"], ["143", "1634", "21154143"], ["143", "163421154", "143"]]) 的元素数组的数组，以及将它们组合成输出格式的包装器。 ([":143:1634:21154:143:", ":143:1634:21154143:", ":143:163421154:143:"])。在我看来，这是工作的适当分解。数组很好用，我们可以用它们做更多的事情。但这不是唯一的方法。我们可以直接将其更改为 return 字符串：

const make = (target, sources) =>
  target .length == 0
    ? ['']
    : sources 
       .filter (s => target .startsWith (s)) 
       .flatMap (s => make (target .slice (s .length), sources) .map (r => `:${s}${r}` +  (r ? '' : ':')))

const nums = "143163421154143"
const predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"]

console .log (make (nums, predefinedNumbers))

请注意，这里在构建字符串时还有一些额外的复杂性。这是因为尾随“:”。我们只想在现有字符串为空时在第一步添加它。（我们总是添加领先的。）

数组搜索和切片

Array searching and slicing

javascript

algorithm

permutation