Эта проблема похожа на эту проблему с leetcode. Вот ответ, который я отправил для этой проблемы на leetcode (для объяснения проверьте github и video ).
Итак, самое первое, что нам нужно, это какой-то способ удержания отображений цифры, и мы можем использовать карту для этого:
private Map<Integer, String> getDigitMap() {
return Stream.of(
new AbstractMap.SimpleEntry<>(2, "abc"),
new AbstractMap.SimpleEntry<>(3, "def"),
new AbstractMap.SimpleEntry<>(4, "ghi"),
new AbstractMap.SimpleEntry<>(5, "jkl"),
new AbstractMap.SimpleEntry<>(6, "mno"),
new AbstractMap.SimpleEntry<>(7, "pqrs"),
new AbstractMap.SimpleEntry<>(8, "tuv"),
new AbstractMap.SimpleEntry<>(9, "wxyz"))
.collect(Collectors.toMap(AbstractMap.SimpleEntry::getKey,
AbstractMap.SimpleEntry::getValue));
}
Приведенный выше метод готовит карту, и следующий метод, который я хотел бы использовать, состоит в том, чтобы обеспечить отображение для предоставленной цифры:
private String getDigitMappings(String strDigit, Map<Integer,String> digitMap) {
int digit = Integer.valueOf(strDigit);
return digitMap.containsKey(digit) ? digitMap.get(digit) : "";
}
Эту проблему можно решить с помощью обратного отслеживания, а решение для обратного отслеживания обычно имеет структуру, в которой сигнатура метода будет содержать: контейнер результатов, временные результаты, исходный источник с индексом и т. Д. Таким образом, структура метода будет иметь вид:
private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
// Condition to populate temp value to result
// explore other arrangements based on the next input digit
// Loop around the mappings of a digit and then to explore invoke the same method recursively
// Also need to remove the digit which was in temp at last so as to get proper value in temp for next cycle in loop
}
И теперь тело метода можно заполнить как (результат будет сохранен в списке, temp в строителе строк и т. Д.)
private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
if(start >= digits.length()) { // condition
result.add(temp.toString());
return;
}
String letters = getDigitMappings(digits.substring(start, start + 1), digitMap); // mappings of a digit to loop around
for (int i = 0; i < letters.length(); i++) {
temp.append(letters.charAt(i));
compute(result, temp, digits, start+1, digitMap); //explore for remaining digits
temp.deleteCharAt(temp.length() - 1); // remove last in temp
}
}
И, наконец, метод может быть вызван как:
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits == null || digits.length() == 0) return result;
compute(result, new StringBuilder(), digits, 0, getDigitMap());
return result;
}
Теперь максимальные сопоставленные символы для цифры могут быть 4 (например, 9 имеет wxyz), а обратный поиск включает в себя исчерпывающий поиск, чтобы исследовать все возможные схемы (дерево пространства состояний), поэтому для цифры размера n мы будем иметь 4x4x4....n times то есть сложность будет O(4^n).