Массив Перестановки / Комбинации

Question

Я пытаюсь найти лучший способ проверить, является ли строка либо

1. равно значению массива в одном индексе.
2. равно перестановкемассив
3. Равен любой комбинации значений.
   3.1 Это может включать в себя комбинацию значений массива с пробелами между словами.
   3.2 Сюда может входить комбинация значений массива без пробелов между словами.
4. У САМОСТОЯТЕЛЬНЫХ МОДУЛЕЙ ЗНАЧЕНИЙ НЕ ИМЕЕТСЯ ПРОСТРАНСТВ ИЛИ СПЕЦИАЛЬНЫХ ХАРАКТЕРОВ
5. Каждое значение массива будетбыть уникальный.Повторяющиеся значения отсутствуют.
6. В строке никогда не будет более двух слов.
7. В строке никогда не будет специальных символов, но могут быть пробелы.

Есть идеи?

Пример данных:

var stringExample = "application Name";

var arrayExample = ['app', 'application', 'name'];

Псуедо:

for (var i = 0; i < arrayExample.length; i++) {
     if (stringExample.toLower() == arrayExample[i]) {
          return true;
     } elseif (stringExample.toLower() == "Any Combination of array values with spaces or
                       without spaces in between") { return true };
}

Answer 1

Очевидно, что слово во входной строке может потребовать объединения двух или более элементов массива, чтобы считаться совпадающими.Это, вероятно, самая сложная часть требования.

Во-вторых, кажется, что как только слово соответствует (или сочетается) со значением (ями) массива, эти элементы массива больше не должны использоваться дляеще один матч.

Я бы предложил использовать простой объект для хранения значений массива в качестве свойств.Это позволит быстро найти, и удаление (для удовлетворения второго пункта выше) также может быть сделано довольно эффективно.Для реализации первого требования я бы придерживался подхода грубой силы.В качестве альтернативы вы можете построить дерево суффиксов , но вам потребуется огромный вклад, прежде чем вы получите от него выгоду, поэтому я не буду предлагать это.

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

Вот решение EcmaScript 3, которое реализует эти идеи:

function match(str, arr) {
    var words = str.toLowerCase().split(/\s+/);
    var keys = {};
    for (var i = 0; i < arr.length; i++) keys[arr[i].toLowerCase()] = 1;

    function recur(i) {
        if (i >= words.length) return true;
        var word = words[i];
        if (keys[word]) { // Try full match first - relatively fast operation
            keys[word] = 0;
            if (recur(i+1)) return true;
            keys[word] = 1; // backtrack: restore key
        } else { // Try partial match - relatively slow operation
            for (var key in keys) {
                if (!keys[key] || word.slice(0, key.length) !== key) continue;
                keys[word] = 0;
                words[i] = word.slice(key.length);
                if (recur(i)) return true;
                words[i] = word; // backtrack: restore word
                keys[word] = 1; // backtrack: restore key
            }
        }
        return false;
    }
    return recur(0);
}

var str = "application Name";
var arr = ['nam', 'me', 'applica', 'app', 'lication', 'na'];
console.log(match(str, arr));

Answer 2

Таким образом, сопоставить всю строку и ее части, если они разделены пробелом, довольно просто:

var stringExample = "application Name";
var example2 = "app King";
var example3 = "application";
var example4 = "some random string";
var arrayExample = ['app', 'application', 'name'];

function findMatch(string, array){
  var a1 = string.toLowerCase().split(" ");
  var match = false;
  // create array simply to check for each string part if it is in the array
  var matches  = [];
  for(var j = 0; j < a1.length; j++){
    matches.push(false);
  }
  for(var i = 0; i < array.length; i++){
    // Checking for complete Match
    if(string.toLowerCase() === array[i].toLowerCase()){
      match = true;
      break;
    }
    // Checking for partly matches
    for(var j = 0; j < a1.length; j++){
      if(a1[j] === array[i].toLowerCase()){
        matches[j] = true;
      }
    }
  }
  // if all parts of the string have a match, return true
  if(matches.every(function(b){return b === true;})){
    match = true;
  }
  return match;
}

console.log(stringExample + " does match: " + findMatch(stringExample, arrayExample));
console.log(example2 + " does match: " + findMatch(example2, arrayExample));
console.log(example3 + " does match: " + findMatch(example3, arrayExample));
console.log(example4 + " does match: " + findMatch(example4, arrayExample));