Найти все комбинации токенов, которые образуют данную строку

Question

Мне нужно найти все возможные комбинации ключей данной карты, включая дубликаты, которые образуют определенную строку. Проблема выглядит довольно простой, но я даже не знаю, с чего начать.

---

Я уже пробовал перебор всех существующих комбинаций, которые потерпели неудачу, когда входная строка не содержала все существующие ключи, не говоря уже о том, что они были ужасно неэффективны.

Следующим моим предположением было использование рекурсивных функций. К сожалению, я далеко не лучший, когда дело доходит до их использования; после пары часов слепой игры и поиска в Google мне наконец-то хватило и я решил задать вопрос здесь.

Вот мой код, лишенный небольшой логики c, которая у меня была:

var map = {
    "01":  "A",
    "100": "B",
    "101": "C",
    "10":  "D",
    "111": "E",
    "000": "F"
}

function waysToDecode(input, keys, values) {
    ...
    return arrayOfPossibleDecodings;
}

Вход:

>> waysToDecode("1010110", Object.keys(map), Object.values(map));

Выход:

["DCD", "CAD"]

Любая помощь будет оценена. Кроме того, мне интересно, если этот или подобный алгоритм имеет имя; проблема выглядит достаточно общей, чтобы ее можно было решить.

Answer 1

Надеюсь, это поможет.

const map = {
  "01":  "A",
  "100": "B",
  "101": "C",
  "10":  "D",
  "111": "E",
  "000": "F"
};

// recursive function. Splits the string into 2 possible ways at each level
// a two possibility / a three. call the function itself with remaning part of the string
const buildTree = (input) => {
	if (!input) {
  	return [];
  }
	// if input length is less than 2 return
  // we came down the wrong path
	if (input.length < 2) { 
  	return;
  }
  
	if (input.length == 2 || input.length == 3 ) {
  	// if its a valid entry we will have the mapped value for the key, if not its a invlaid path
    if (map[input]) {
      return [map[input]];
    } else {
    	return;
    }
  }

	// if we have length more than 3 then we try to break it into 2 paths
  // 1. with length 2
  // 2. with length 3
  let valueTwo = map[input.slice(0, 2)];
  let valueThree = map[input.slice(0, 3)];
  let possibleCombinations = [];
  if (valueTwo) {
  	let subCombinations = buildTree(input.slice(2));
    if (subCombinations) {
    	possibleCombinations = [...subCombinations.map(value => `${valueTwo}${value}`)];
    }
  }
  if (valueThree) {
  	let subCombinations = buildTree(input.slice(3));
    if (subCombinations) {
    	possibleCombinations = [...possibleCombinations, ...subCombinations.map(value => `${valueThree}${value}`)];
    }
  }
  
  return possibleCombinations;
};

function waysToDecode(input) {
    let arrayOfPossibleDecodings = buildTree(input);
    return arrayOfPossibleDecodings || [];
}

document.write(waysToDecode("1010110"));