Letter Combinations of a Phone Number

Q: Độ phức tạp thời gian của bài toán Tổ hợp chữ cái từ số điện thoại là bao nhiêu?

O(4^n · n) cho n chữ số: có thể có 4^n chuỗi khi mỗi chữ số là 7 hoặc 9, và cần n bước để viết mỗi chuỗi. Đó là kích thước của đầu ra, nên không lời giải nào có thể làm tốt hơn. Quay lui cần O(n) bộ nhớ bổ sung ngoài phần đầu ra.

Trung bìnhQuay lui

+10

Trên bàn phím điện thoại, mỗi chữ số từ 2 đến 9 tương ứng với một vài chữ cái: 2 là abc, 3 là def, 4 là ghi, 5 là jkl, 6 là mno, 7 là pqrs, 8 là tuv và 9 là wxyz.

Bạn nhận được một chuỗi digits. Chọn một chữ cái cho mỗi chữ số, giữ nguyên thứ tự các chữ số, bạn sẽ có một chuỗi mà các phím có thể nhập. Trả về tất cả các chuỗi như vậy, được sắp xếp theo thứ tự từ điển.

Hàm

letterCombinations(digits: string) → string-array

digitsstring: các chữ số bạn đã nhấn, mỗi chữ số từ 2 đến 9
Trả vềstring-array: mọi chuỗi mà các phím có thể nhập, theo thứ tự từ điển

Ràng buộc

1 ≤ digits.length ≤ 4
Mỗi ký tự trong digits là một chữ số từ 2 đến 9.
Đáp án chứa tối đa 4⁴ = 256 chuỗi.

Ví dụ

Đầu vào: digits = "23"
Đầu ra: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Giải thích: 2 cung cấp a, b, c và 3 cung cấp d, e, f. Mỗi chữ cái đầu ghép với mỗi chữ cái thứ hai: 3 × 3 = 9 chuỗi (string), được sắp xếp sao cho chữ cái đầu thay đổi chậm nhất.

Đầu vào: digits = "94"
Đầu ra: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Giải thích: 9 có bốn chữ cái và 4 có ba chữ cái, nên có 4 × 3 = 12 chuỗi. Cả ba chuỗi bắt đầu bằng w đều đứng trước chuỗi đầu tiên bắt đầu bằng x.

Câu hỏi mở rộng

Giả sử bạn chỉ muốn những tổ hợp tạo thành từ có thật trong từ điển. Làm thế nào để tránh tạo trước tất cả các chuỗi 4^n?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Câu trả lời chứa tối đa 4^n chuỗi, vì vậy mọi lời giải đều cần ít nhất từng ấy công sức để ghi chúng ra. Điều quan trọng là tạo ra mỗi lựa chọn đúng một lần, không bỏ sót hay lặp lại lựa chọn nào. Đó là cách quay lui trên cây quyết định có một tầng cho mỗi chữ số, trong đó mỗi nút lá là một câu trả lời.

Tạo chuỗi từng chữ số một

Ý tưởng

Bắt đầu với một danh sách chứa một chuỗi rỗng, rồi mở rộng danh sách từng chữ số một. Với "23", chữ số 2 biến chuỗi đó thành a, b, c, rồi chữ số 3 mở rộng từng chuỗi bằng d, e và f, tạo ra chín chuỗi.

Thứ tự vẫn được sắp xếp. Nếu danh sách đã được sắp xếp trước một chữ số, bạn mở rộng các tiền tố theo thứ tự đó, rồi mở rộng từng tiền tố bằng các chữ cái ứng với phím của nó từ trái sang phải: tiền tố đứng trước vẫn giữ nguyên vị trí, còn các tiền tố giống nhau được sắp xếp theo chữ cái mới.

Khối lượng công việc tỷ lệ với kích thước của kết quả, nhưng khi bạn xây dựng một cấp, toàn bộ cấp trước đó vẫn nằm trong bộ nhớ.

Thuật toán

Bắt đầu với combos = [""], một tiền tố rỗng.
Với mỗi chữ số, tạo một danh sách mới: với mỗi tiền tố trong combos và mỗi chữ cái trên phím tương ứng với chữ số đó, thêm prefix + letter.
Thay combos bằng danh sách mới.
Sau chữ số cuối cùng, trả về combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

Quay lui trên cây quyết định

Ý tưởng

Các đáp án là những lá của cây quyết định. Gốc là chuỗi rỗng, mỗi tầng thêm một chữ cái của chữ số tiếp theo: với "23", gốc có các nút con a, b, c, mỗi nút lại có các nút con tương ứng với d, e, f.

Duyệt cây theo chiều sâu bằng một bộ đệm duy nhất, path. Ở tầng i, chọn một chữ cái của digits[i] bằng cách nối chữ cái đó vào, khám phá bằng cách gọi đệ quy với i+1, rồi hoàn tác bằng cách xóa chữ cái đó. Việc hoàn tác giúp một bộ đệm duy nhất dùng được cho cả cây: sau ad, ae và af, thao tác lấy phần tử ra đưa path trở lại a, rồi về chuỗi rỗng, sẵn sàng cho b. Khi i chạm đến cuối digits, hãy lưu một bản sao.

Độ phức tạp thời gian vẫn là O(4^n · n), nhưng bộ nhớ phụ chỉ gồm bộ đệm và ngăn xếp lời gọi, O(n).

Thuật toán

Giữ path và result trống.
Định nghĩa backtrack(i): nếu i bằng độ dài của digits, hãy lưu một bản sao của path rồi trả về.
Nếu không, lần lượt với mỗi chữ cái trên khóa tương ứng với digits[i]: thêm chữ cái đó vào path, gọi backtrack(i+1), rồi xóa chữ cái đó.
Gọi backtrack(0) rồi trả về result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

Lỗi thường gặp và trường hợp biên

Giả sử mọi phím đều có ba chữ cái. Lấy ba chữ cái từ chỉ số (d-2)*3 trong bảng chữ cái sẽ bỏ sót s ở số 7 và bắt đầu số 8 bằng s. Hãy viết bảng phím dưới dạng bảng.
Quên hoàn tác. path cứ dài thêm, và đáp án thứ hai cho "23" lại là ade thay vì ae.
Lưu bộ đệm thay vì bản sao. Trong Python, result.append(path) lưu cùng một danh sách chín lần, và đến cuối thì danh sách đó rỗng.
Thử các chữ cái của một phím từ phải sang trái, hoặc nối chuỗi từ một ngăn xếp trong phiên bản lặp. Cả hai cách đều phá vỡ thứ tự sắp xếp.
Trong PHP và R, "23" có thể được nhận dưới dạng số 23. Hãy chuyển nó thành văn bản trước khi lấy chỉ số các ký tự.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán Tổ hợp chữ cái từ số điện thoại là bao nhiêu?

O(4^n · n) cho n chữ số: có thể có 4^n chuỗi khi mỗi chữ số là 7 hoặc 9, và cần n bước để viết mỗi chuỗi. Đó là kích thước của đầu ra, nên không lời giải nào có thể làm tốt hơn. Quay lui cần O(n) bộ nhớ bổ sung ngoài phần đầu ra.

Vì sao thuật toán quay lui trả về các tổ hợp theo thứ tự đã sắp xếp?

Tất cả đáp án đều có cùng độ dài, và phép duyệt theo chiều sâu hoàn tất mọi chuỗi bắt đầu bằng a trước khi chọn b. Điều tương tự cũng đúng ở mọi cấp, miễn là các chữ cái trong mỗi khóa được xét từ trái sang phải. Đó là thứ tự từ điển, nên không cần sắp xếp.

Còn các chữ số 0 và 1 thì sao?

Trên bàn phím điện thoại, các phím 0 và 1 không có chữ cái, phiên bản này chỉ dùng các phím từ 2 đến 9. Nếu chúng có thể xuất hiện, bạn sẽ phải quyết định bỏ qua chữ số đó hay để đáp án trống. Khi phỏng vấn, hãy hỏi xem người ta muốn chọn cách nào.

def letterCombinations(digits):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

digits = "23"

Đầu ra mong đợi

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]