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

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

Примеры:

Input:

Output: 2
Only the strings of the node 1 and 4 contains unique strings.

Подход: выполните dfs на дереве и для каждого узла проверьте, содержит ли строка повторяющийся символ или нет. Если нет, то увеличьте счетчик.

Ниже представлена реализация описанного выше подхода:

Анализ сложности:

• Сложность времени: O (N * Len), где Len - максимальная длина взвешенной строки узла в данном дереве.
  В dfs каждый узел дерева обрабатывается один раз, и, следовательно, сложность из-за dfs составляет O (N), если в дереве всего N узлов. Кроме того, обработка каждого узла включает обход взвешенной строки этого узла, таким образом добавляя сложность O (Len), где Len - длина взвешенной строки. Следовательно, временная сложность O (N * Len).
• Вспомогательное пространство: O (1).
  Никакого дополнительного места не требуется, поэтому сложность пространства постоянна.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.