Задача: 247. Strobogrammatic Number II
Сложность: medium

Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.

Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: n = 2
Output: ["11","69","88","96"]

👨‍💻 Алгоритм:

1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.

2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.

3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private List<List<char>> reversiblePairs = new List<List<char>> {
        new List<char>{'0', '0'}, new List<char>{'1', '1'}, 
        new List<char>{'6', '9'}, new List<char>{'8', '8'}, new List<char>{'9', '6'}
    };
    
    public List<string> GenerateStroboNumbers(int n, int finalLength) {
        if (n == 0) {
            return new List<string> { "" };
        }
        
        if (n == 1) {
            return new List<string> { "0", "1", "8" };
        }
        
        List<string> prevStroboNums = GenerateStroboNumbers(n - 2, finalLength);
        List<string> currStroboNums = new List<string>();
        
        foreach (string prevStroboNum in prevStroboNums) {
            foreach (List<char> pair in reversiblePairs) {
                if (pair[0] != '0' || n != finalLength) {
                    currStroboNums.Add(pair[0] + prevStroboNum + pair[1]);
                }
            }
        }
        
        return currStroboNums;
    }
    
    public List<string> FindStrobogrammatic(int n) {
        return GenerateStroboNumbers(n, n);
    }
}

Ставь 👍 и забирай 📚 Базу знаний