Đề bài:
Cho một chuỗi chứa các chữ số từ 2 đến 9 (bao gồm), trả về tất cả các kết hợp chữ cái có thể biểu diễn bởi các số đó. Trả về kết quả theo bất kỳ thứ tự nào.
Một bảng ánh xạ từ số đến chữ cái (giống như trên các nút điện thoại) được đưa ra dưới đây. Lưu ý rằng số 1 không ánh xạ đến bất kỳ chữ cái nào.
Ví dụ 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Ví dụ 2:
Input: digits = "" Output: []
Ví dụ 3:
Input: digits = "2" Output: ["a","b","c"]
Ràng buộc:
- 0 <= độ dài của chuỗi digits <= 4
- digits[i] là một chữ số nằm trong khoảng từ ‘2’ đến ‘9’.
Cách 1: DFS
Giải thích thuật toán bằng C++
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty())
return {};
vector<string> ans;
dfs(digits, 0, "", ans);
return ans;
}
private:
const vector<string> digitToLetters{"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
void dfs(const string& digits, int i, string&& path, vector<string>& ans) {
if (i == digits.length()) {
ans.push_back(path);
return;
}
for (const char letter : digitToLetters[digits[i] - '0']) {
path.push_back(letter);
dfs(digits, i + 1, move(path), ans);
path.pop_back();
}
}
};
Đoạn mã trên triển khai thuật toán để tạo ra tất cả các kết hợp chữ cái có thể biểu diễn bởi một chuỗi số.
1. Hàm `letterCombinations` nhận vào một chuỗi `digits` và trả về một vector chứa tất cả các kết hợp chữ cái tương ứng. Trước khi bắt đầu, hàm kiểm tra xem `digits` có rỗng không. Nếu rỗng, ta trả về vector rỗng.
2. Một vector `ans` được khởi tạo để lưu trữ các kết hợp chữ cái.
3. Hàm `dfs` (depth-first search) được sử dụng để thực hiện việc tạo ra các kết hợp chữ cái. Hàm này nhận vào các tham số sau:
– `digits`: chuỗi số ban đầu.
– `i`: chỉ số hiện tại đang xét trong `digits`.
– `path`: chuỗi đã được xây dựng cho đến thời điểm hiện tại.
– `ans`: vector chứa các kết hợp chữ cái.
4. Trong hàm `dfs`, nếu `i` bằng độ dài của `digits`, tức là đã xét hết tất cả các số trong `digits`, ta thêm `path` vào vector `ans` và kết thúc hàm.
5. Trong vòng lặp `for`, ta lặp qua từng chữ cái tương ứng với số `digits[i]`. Chữ cái này được truy xuất thông qua `digitToLetters[digits[i] – ‘0’]`. Ví dụ: nếu `digits[i]` là ‘2’, ta sẽ lặp qua các chữ cái ‘a’, ‘b’ và ‘c’.
6. Trong vòng lặp, ta thực hiện các bước sau:
– Thêm chữ cái vào `path`.
– Gọi đệ quy hàm `dfs` với `i` tăng lên 1, `path` được chuyển bằng giá trị hiện tại và `ans`.
– Sau khi đệ quy hoàn thành, ta loại bỏ chữ cái cuối cùng khỏi `path` để chuẩn bị cho vòng lặp tiếp theo.
7. Sau khi kết thúc hàm `dfs`, ta trả về vector `ans` chứa tất cả các kết hợp chữ cái tương ứng với `digits`.
Thuật toán này sử dụng phương pháp đệ quy (DFS) để tạo ra tất cả các kết hợp chữ cái từ chuỗi số. Bằng cách duyệt qua từng số trong chuỗi `digits` và lặp qua các chữ cái tương ứng, ta xây dựng từng kết hợp chữ cái và lưu trữ chúng trong vector `ans`.
Giải thích thuật toán bằng Java
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty())
return new ArrayList<>();
List<String> ans = new ArrayList<>();
dfs(digits, 0, new StringBuilder(), ans);
return ans;
}
private static final String[] digitToLetters = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
private void dfs(String digits, int i, StringBuilder sb, List<String> ans) {
if (i == digits.length()) {
ans.add(sb.toString());
return;
}
for (final char c : digitToLetters[digits.charAt(i) - '0'].toCharArray()) {
sb.append(c);
dfs(digits, i + 1, sb, ans);
sb.deleteCharAt(sb.length() - 1);
}
}
}
Giải thích thuật toán bằng Python
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
digitToLetters = ['', '', 'abc', 'def', 'ghi',
'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
ans = []
def dfs(i: int, path: List[chr]) -> None:
if i == len(digits):
ans.append(''.join(path))
return
for letter in digitToLetters[ord(digits[i]) - ord('0')]:
path.append(letter)
dfs(i + 1, path)
path.pop()
dfs(0, [])
return ans
Cách 2: Iterative
Giải thích thuật toán bằng C ++
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty())
return {};
vector<string> ans{""};
const vector<string> digitToLetters{"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
for (const char d : digits) {
vector<string> temp;
for (const string& s : ans)
for (const char c : digitToLetters[d - '0'])
temp.push_back(s + c);
ans = move(temp);
}
return ans;
}
};
Đoạn mã trên triển khai một thuật toán để tạo ra tất cả các kết hợp của các chữ cái tương ứng với một số điện thoại được nhập vào dưới dạng chuỗi số.
Thuật toán này sử dụng một vector `ans` để lưu trữ các chuỗi kết hợp. Ban đầu, `ans` được khởi tạo với một chuỗi rỗng, đại diện cho trường hợp khi `digits` là chuỗi rỗng.
Một vector `digitToLetters` được sử dụng để ánh xạ các chữ số từ 2 đến 9 với các chuỗi chữ cái tương ứng. Ví dụ, `digitToLetters[2]` chứa chuỗi “abc”, `digitToLetters[3]` chứa chuỗi “def”, và cứ như vậy.
Tiếp theo, thuật toán sử dụng hai vòng lặp lồng nhau để tạo ra tất cả các kết hợp của các chữ cái tương ứng với các chữ số trong `digits`. Vòng lặp bên ngoài duyệt qua từng chữ số trong `digits`, và vòng lặp bên trong duyệt qua từng chữ cái tương ứng với chữ số hiện tại.
Trong vòng lặp bên trong, một vector tạm thời `temp` được tạo ra để lưu trữ các kết hợp mới. Với mỗi chuỗi trong `ans`, vòng lặp duyệt qua từng chữ cái tương ứng với chữ số hiện tại (`digitToLetters[d – ‘0’]`) và thêm các chuỗi mới vào `temp` bằng cách ghép nối chữ cái với chuỗi hiện có.
Sau khi hoàn thành vòng lặp bên trong, `temp` chứa tất cả các kết hợp mới được tạo ra từ `ans`. Kết quả của `temp` được gán lại cho `ans` bằng cách sử dụng `move` để di chuyển các giá trị của `temp` vào `ans`.
Cuối cùng, sau khi hoàn thành vòng lặp bên ngoài, `ans` chứa tất cả các kết hợp của các chữ cái tương ứng với `digits`. `ans` được trả về là kết quả của thuật toán.
Ví dụ, nếu `digits = “23”`, thì `digitToLetters[2]` tương ứng với chuỗi “abc” và `digitToLetters[3]` tương ứng với chuỗi “def”. Ban đầu, `ans` chứa một chuỗi rỗng. Trong vòng lặp bên ngoài, chữ số “2” được xử lý. Vòng lặp bên trong duyệt qua các chữ cái “a”, “b” và “c” và thêm các chuỗi “a”, “b” và “c” vào `temp`. Sau đó, `temp` được gán lại cho `ans` và `ans` chứa các chuỗi “a”, “b” và “c”. Tiếp theo, chữ số “3” được xử lý. Vòng lặp bên trong duyệt qua các chữ cái “d”, “e” và “f” và thêm các chuỗi “ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce” và “cf” vào `temp`. Sau đó, `temp` được gán lại cho `ans` và `ans` chứa tất cả các chuỗi kết hợp “ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce” và “cf”. Cuối cùng, `ans` được trả về là kết quả của thuật toán.
Giải thích thuật toán bằng Java
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty())
return new ArrayList<>();
List<String> ans = new ArrayList<>();
ans.add("");
final String[] digitToLetters = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
for (final char d : digits.toCharArray()) {
List<String> temp = new ArrayList<>();
for (final String s : ans)
for (final char c : digitToLetters[d - '0'].toCharArray())
temp.add(s + c);
ans = temp;
}
return ans;
}
}
Giải thích thuật toán bằng Python
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
ans = ['']
digitToLetters = ['', '', 'abc', 'def', 'ghi',
'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
for d in digits:
temp = []
for s in ans:
for c in digitToLetters[ord(d) - ord('0')]:
temp.append(s + c)
ans = temp
return ans
0 / 5 - (0 Đánh Giá)