Переставить буквы в одну строку, чтобы соответствовать порядок букв во вторую строку


У меня есть решение следующей проблемы, которые я хотел бы знать, если есть способ я могу уменьшить сложность выполнения.

Направления: переставить буквы первой строки, чтобы соответствовать порядок букв во вторую строку. Если буква в первой строке нет во второй строке, Добавить его в конце дозаказа.

Пример ввода: 'кричит', 'суп' Пример вывода: 'ssouht'

Мой код выглядит следующим образом:

const reOrderLetters = (string1,string2) => {
  let tailString = '';
  let newString = '';
  const mapped = {};

  for (let i=0;i<string1.length;i++) {
    let char = string1[i];
    if (string2.indexOf(char) !== -1) {
      if (!mapped[char]) {
        mapped[char] = char;
      } else {
        mapped[char] = mapped[char] += char;
      }
    } else {
      tailString += char;
    }
  }
  for (let i=0;i<string2.length;i++) {
    let char = string2[i];
    if (mapped[char]) {
      if (mapped[char].length > 1 && string2.slice(i+1).indexOf(char) !== -1) {
        newString += mapped[char].slice(mapped[char].length-1);
        mapped[char] = mapped[char].slice(0,mapped[char].length-1);
      } else {
        newString += mapped[char];
      }
    }
  }
  return newString += tailString;

}


118
0
задан 3 апреля 2018 в 06:04 Источник Поделиться
Комментарии
1 ответ

Ваш код довольно хорошо, за исключением использования indexOf(char)Как это может быть довольно дорогим: O(string2.length). Вот как я бы сделал это, чтобы избежать использования этого. Предполагая, что хранилище HashMap доступ O(1) а n-максимальная длина между двумя строками, моя реализация работает в O(n)



function characterCount (str) {
var chars = {};

for (var i = 0; i < str.length; i ++) {
chars[str[i]] = (chars[str[i]] || 0) + 1;
}

return chars;
}

function reOrderLetters (str1, str2) {
var count1 = characterCount(str1); // O(n)
var count2 = characterCount(str2); // O(n)
var result = [];
var seenCount = {}

for (var i = 0; i < str2.length; i++) {
var char = str2[i];
seenCount[char] = (seenCount[char] || 0) + 1;

if (count1.hasOwnProperty(char)) {
var remaining = count1[char] % count2[char];
var toRepeat = Math.floor(count1[char] / count2[char]);

if (seenCount[char] <= remaining) {
toRepeat = Math.ceil(count1[char] / count2[char]);
}

result.push(char.repeat(toRepeat));
}
}

for (var i = 0; i < str1.length; i++) {
var char = str1[i];

if (count2.hasOwnProperty(char) == false) {
result.push(char.repeat(count1[char]));
count2[char] = true;
}
}

return result.join("");
}

console.log(reOrderLetters("shouts", "soups") == "sousht")
console.log(reOrderLetters("aa", "aaaa") == "aa")
console.log(reOrderLetters("aabbbba", "abab") == "aabbabb")




1
ответ дан 3 апреля 2018 в 07:04 Источник Поделиться