В древние времена, когда не было смартфонов, на мобильных телефонах была клавиатура с цифрами от 0 до 9 и некоторыми специальными символами, такими как *, # и т. Д. У Digits также были некоторые алфавиты, чтобы обеспечить возможность обмена сообщениями. Как здесь, если мы хотим ввести a, b, c, нам нужно будет нажать цифру 2 один, два и три раза соответственно. Итак, мы можем напечатать все наше сообщение, используя цифры 2–9, поскольку они охватывают весь диапазон набора символов, то есть от a до z.

Постановка задачи:

Существует проблема, которую часто задают на собеседовании по кодированию: нам дается строка, содержащая цифры от 2-9 включительно, возвращаются все возможные комбинации букв, которые может представлять число.

Например:
цифры = «23»
Вывод: [«ad», «ae», «af», «bd», » be »,« bf »,« cd »,« ce »,« cf »]

Посмотрим, как мы можем решить эту проблему.

Подход

Прежде всего, очевидно, что все цифры от 2 до 9 включительно могут представлять набор алфавитов, которые они могут представлять. Некоторые цифры, такие как 2, 3, 4, 5, 6 и 8, могут представлять три алфавита, в то время как 7 и 9 могут представлять 4 алфавита каждая. Итак, сначала нам нужно сохранить то, что все алфавиты могут быть представлены одной цифрой.

Массив символов

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

private static char[] alphabet = new char[10];
char c = 'a'; //starting character
for(int i=2; i<10; i++){
    alphabet[i]=c;
    c = (i==7||i==9)?(char)(c+4):(char)(c+3);
}

Теперь давайте рассмотрим несколько примеров, чтобы лучше понять.

Пример 1: digits = «»
В этом случае строка цифр равна нулю, поэтому мы не можем составлять комбинации букв с нулевыми цифрами, поэтому возвращаем пустой список.

Пример 2: digits = «2»
В этом случае строка цифр состоит только из одной цифры, поэтому мы можем выбрать только буквы, разрешенные для цифры 2. Поскольку цифра 2 может представлять три алфавита, поэтому возможными комбинациями будут «a», «b» и «c», выбираемые по одной.
Аналогичным образом, если цифры = «7», тогда, поскольку цифра 7 может представляют четыре алфавита, поэтому возможными комбинациями будут «p», «q», «r» и «s», выбираемые по одному.

Пример 3: цифры = «23»
В этом случае строка цифр состоит из двух цифр, то есть 2 и 3. И 2, и 3 могут представлять 3 алфавита.
Если мы выберем первый алфавит, соответствующий цифре 2, то есть «а», то мы сможем перейти к следующей цифре 3 и проверить все возможные представления.

Итак, установив 2 = ‘a’, наше дерево будет выглядеть так:

Зафиксировав 2 как «a», у нас есть три варианта для 3, то есть (d, e и f). Следовательно, возможны (3 + 3 + 3) комбинации, то есть 9 комбинаций, после фиксации 2 как a, b или c по одной. Комбинации: [ad, ae, af, bd, be, bf, cd, ce, cf]

Пример 4: цифры = «27»
В этом случае строка цифр состоит из двух цифр, т. е. 2 и 3. 2 могут представлять 3 алфавита, а 7 - 4 алфавита.
Если мы выберем первый алфавит, соответствующий цифре 2, то есть «a», то мы сможем перейти к следующей цифре 7 и проверить все возможные представления = [ap, aq, ar, as]. Таким же образом, как и выше, полные возможности будут (4 + 4 + 4) = 12.

Есть одно наблюдение: когда у нас есть две цифры с 3-мя возможными представлениями символов (например, 23), тогда нет. возможных комбинаций = 3². Когда есть одна цифра, представляющая 3 алфавита, и одна цифра, представляющая 4 алфавита, тогда нет. возможных комбинаций = 3 * 4

Давайте возьмем пример трех цифр, чтобы обобщить нет. возможных комбинаций.

Таким образом, обобщенная формула для no. комбинаций букв, возможных для строки цифр = 3 ^ n * 4 ^ m, где n = no. цифр, что представляет ровно 3 алфавита и m = нет. цифр, что представляет ровно 4 алфавита.

В приведенном выше примере 273 = нет. комбинаций = 3² * 4¹ = 36.

Анализ кода

Вышеупомянутую проблему можно решить с помощью рекурсии и поиска с возвратом. Мы начинаем с пустого StringBuilder в начале. Каждая цифра в строке цифр имеет возможные представления алфавитов, которые она может представлять.

Инициализируйте start = 0, представляя текущую позицию строки цифр, и список будет пустым

private void recursion(int start, String digits, StringBuilder sb, List<String> list){
        //if we have used all digits of digits string, all the current letter combination in the list and return
        if(start==digits.length()){
            list.add(new String(sb.toString()));
            return;
        }
        
        //compute the bound for current digit, i.e. how many alphabets current digit can represent, if current digit is 7 or 9, then it can represent 4 alphabets and the remaining digits can represent 3 alphabets
        int bound = digits.charAt(start)-'0'==7 || digits.charAt(start)-'0'==9 ? 4: 3;
        
        //starting from first alphabet for current digit to the last alphabet it can represent
        for(int j=0; j<bound; j++){
            //add the current alphabet to the string builder
            sb.append((char)(alphabet[digits.charAt(start)-'0']+j));
            //recurse for the next digit of digits string
            recursion(start+1, digits, sb, list);
            //backtrack and delete the current alphabet from the string builder
            sb.deleteCharAt(sb.length()-1);
        }
    }

Сложность времени = O (3 ^ n * 4 ^ m), так как мы объясняли это множество комбинаций выше.
Сложность пространства = O (3 ^ n * 4 ^ m), дополнительное место для хранения этих многочисленных комбинаций.

Ребята, очень надеюсь, что эта статья окажется для вас полезной! Если у вас все еще есть какие-либо вопросы, вы можете обсудить их в разделе комментариев ниже.

Большое спасибо за то, что уделили время этому блогу.

Пожалуйста, поделитесь им с коллегами и аплодируйте за то, что выразили признательность! :)