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

Эта проблема

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

Примечание.

  1. 1 <= words.length <= 1000
  2. 1 <= words[i].length, chars.length <= 100
  3. Все строки содержат только строчные буквы английского алфавита.

Пример 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Пример 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Решение

Проще говоря, мы собираемся создать переменную счетчика, построить цикл по массиву слов, который создает объекты из символов, а затем перебрать каждое слово в словах, чтобы определить, подходит оно или нет. Если он хороший, мы добавим его длину к нашему счетчику и вернем окончательный счет в конце. Давайте разберемся с этим!

Во-первых, давайте создадим нашу переменную счетчика - мы назовем эту finalCount, поскольку мы возвращаем ее в конце как окончательный счет. Давайте также создадим переменную с именем charObj, которая в конечном итоге будет содержать объект символа, но пока не будет иметь значения.

Перейдем к нашему внешнему циклу for. Начиная с индекса 0, мы перебираем каждое слово в массиве слов. Поскольку каждый символ в char может использоваться только один раз при формировании хорошего слова, мы знаем, что любое слово, длина которого больше, чем длина char, не может быть хорошим. Мы сэкономим время на этих словах и продолжим переходить через внешний цикл к следующему слову вместо того, чтобы тратить время на наш (еще не созданный) внутренний цикл, когда это произойдет.

Мы собираемся отслеживать, какие символы из char мы уже сравнили, поэтому мы будем создавать новый объект символа во внешнем цикле всякий раз, когда мы начинаем перебирать новое слово, чтобы гарантировать, что количество каждого символа в char равно сбросить в исходное состояние. У нас будет отдельная вспомогательная функция (включенная в наше окончательное решение) под названием makeCharObj, которая создаст объект символа и присвоит значение нашей уже созданной переменной charObj.

var countCharacters = function(words, chars) {
    let finalCount = 0;
    let charObj;
    for (let i = 0; i < words.length; i++) {
        if (words[i].length > chars.length) continue;
        charObj = makeCharObj(chars);
    }
}

Перейдем к нашему внутреннему циклу for! Мы будем перебирать каждое слово слов, при этом увеличивая переменную j, начиная с индекса 0. Чтобы сделать наш код немного чище, мы можем создать переменную с именем char, равную словам [i] [j], или каждому символу в каждой строке массива.

Теперь нам просто нужен условный оператор, чтобы определить, является ли слово хорошим, и добавить его к нашему окончательному счету, если это так. Если мы достигли конца нашего слова и объект символа имеет значение в ключе текущего символа, мы можем добавить длину текущего слова к нашему окончательному счету, так как слово было признано хорошим. В противном случае, если объект символа имеет значение в ключе текущего символа, но мы не находимся в конце текущего слова, мы продолжим цикл до следующей буквы слова, а также уменьшим счетчик значение ключа символьного объекта, поскольку нам нужно отслеживать, сколько раз каждый символ в char используется в слове. Если ни одно из этих условий не выполнено, мы выйдем из внутреннего цикла и перейдем к следующему слову, потому что это означает, что объект символа не имеет значения в ключе текущего символа, поэтому это не делается исключительно до символов в char и поэтому не является хорошей строкой.

for (let j = 0; j < words[i].length; j++) {
         let char = words[i][j];
         if (j == words[i].length - 1 && charObj[char]) {
                finalCount += words[i].length;
         } else if (charObj[char]) {
                charObj[char]--;
         } else {
                break;
         }
}

Единственное, что остается сделать после прохождения обоих циклов, - это вернуть наш окончательный счет! Давайте посмотрим на наше полное решение, включая нашу вспомогательную функцию, со временем выполнения O (n²).

Вы можете найти проблему на LeetCode здесь!

Спасибо за прочтение!