В древние времена, когда не было смартфонов, на мобильных телефонах была клавиатура с цифрами от 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), дополнительное место для хранения этих многочисленных комбинаций.
Ребята, очень надеюсь, что эта статья окажется для вас полезной! Если у вас все еще есть какие-либо вопросы, вы можете обсудить их в разделе комментариев ниже.
Большое спасибо за то, что уделили время этому блогу.
Пожалуйста, поделитесь им с коллегами и аплодируйте за то, что выразили признательность! :)