▲

3

▼

🔑 Бэктрекинг для подсчета уникальных последовательностей плиток (без использования HashSet'a)

leetcoder, 17-02-2025 , 86

Продолжаем череду задач на перебор - 1079. Letter Tile Possibilities.

📜 Описание задачи

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

💡 Идея решения

• Будем использовать бэктрекинг.
• Чтобы избежать проверки на уникальность через HashSet, сначала сортируем плитки, а затем группируем одинаковые плитки в сегменты.
• Далее, с помощью рекурсии, перебираем все возможные последовательности, гарантируя, что одинаковые плитки не будут использоваться более одного раза в одном наборе последовательностей.

🧑‍💻 Подробности подхода

1. Сортировка плиток:
   • Плитки сортируются для того, чтобы одинаковые плитки оказались рядом. Это позволяет нам эффективно группировать их в сегменты.
2. Группировка плиток:
   • Создаем массив сегментов, где каждый элемент представляет собой количество одинаковых плиток.
   • Например, для строки "AAB" сегменты будут равны [2, 1] (2 плитки "A" и 1 плитка "B").
3. Бэктрекинг — для каждого сегмента мы:
   • пытаемся использовать плитку (уменьшаем количество плиток в этом сегменте);
   • рекурсивно исследуем возможные последовательности;
   • и затем восстанавливаем состояние сегмента.
4. Подсчет последовательностей:
   • Каждый раз, когда мы добавляем плитку в последовательность, мы увеличиваем счетчик возможных последовательностей.

⏱️ Асимптотика

• Время: O(n!), где n — длина строки.
  • Сортировка плиток занимает O(n log n)
  • Бэктрекинг потенциально проверяет все возможные перестановки плиток (до O(n!)).
• Память: O(n) для хранения сегментов одинаковых плиток и стека в переборе.

📝 Исходный код

use std::collections::HashSet;

impl Solution {
    pub fn num_tile_possibilities(tiles: String) -> i32 {
        let mut tiles: Vec<_> = tiles.chars().collect();
        tiles.sort_unstable(); // Sort tiles to group identical tiles together

        // Create segments that represent how many tiles of each character exist
        let mut segments: Vec<usize> = tiles
            .chunk_by(|a, b| a == b)
            .map(|c| c.len())
            .collect();

        // Start backtracking to count all possible valid sequences
        Self::backtrack(&mut segments)
    }

    // Backtracking function to count all valid sequences
    fn backtrack(segments: &mut [usize]) -> i32 {
        let mut count = 0; // Start with 0, as we're counting valid sequences only

        for i in 0..segments.len() {
            if segments[i] > 0 {
                // Reduce the count of the current character and recurse
                segments[i] -= 1;
                count += 1 + Self::backtrack(segments); // Add the current tile + recurse
                // Restore the count of the current character (backtrack)
                segments[i] += 1;
            }
        }

        count
    }
}

Tags: #rust #algorithms #backtracking