Word Ladder

Q: Độ phức tạp thời gian của Word Ladder là gì?

Với các nhóm ký tự đại diện, độ phức tạp là O(n × L²) với n từ có độ dài L : mỗi từ có L mẫu gồm L chữ cái. So sánh từng cặp từ có độ phức tạp O(n² × L) , còn thử mọi chuỗi biến đổi bằng tìm kiếm theo chiều sâu thì có độ phức tạp theo hàm mũ.

KhóĐồ thị Hàng đợi

+10

Bạn được cho hai từ, beginWord và endWord, cùng một danh sách từ wordList. Một chuỗi biến đổi bắt đầu bằng beginWord, kết thúc bằng endWord và thay đổi chính xác một chữ cái từ mỗi từ sang từ tiếp theo. Mọi từ sau beginWord đều phải có trong wordList, vì vậy endWord phải có trong danh sách này, còn beginWord thì không nhất thiết phải có.

Trả về số từ trong chuỗi biến đổi ngắn nhất, tính cả hai từ đầu và cuối, hoặc 0 nếu không có chuỗi nào.

Hàm

ladderLength(beginWord: string, endWord: string, wordList: string-array) → integer

beginWordstring: từ đầu tiên của chiếc thang
endWordstring: từ cái thang phải chạm tới
wordListstring-array: các từ mà mọi bước sau phải lấy từ đó
Trả vềinteger: số từ trong chuỗi bậc thang ngắn nhất, hoặc 0 nếu không có

Ràng buộc

1 ≤ beginWord.length ≤ 10
endWord và mọi từ trong wordList có cùng độ dài với beginWord.
1 ≤ wordList.length ≤ 5000
Mọi từ chỉ chứa chữ cái tiếng Anh viết thường.
beginWord != endWord
Các từ trong wordList đều khác nhau. beginWord có thể có hoặc không nằm trong danh sách đó.

Ví dụ

Đầu vào: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Đầu ra: 4
Giải thích: lead và gold khác nhau ở ba chữ cái, nên một thang từ cần ít nhất 4 từ, và lead, load, goad, gold có 4 từ. lend và lewd là những ngõ cụt.

Đầu vào: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Đầu ra: 0
Giải thích: cat, cot, cog chỉ cách dog một ký tự, nhưng dog không có trong danh sách, nên không thể kết thúc ở đó.

Đầu vào: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Đầu ra: 3
Giải thích: ab, ad, cd và ab, cb, cd đều gồm 3 từ. ab cũng có trong danh sách, nhưng điểm bắt đầu chỉ được tính một lần.

Câu hỏi mở rộng

Bạn có thể trả về một chiếc thang ngắn nhất, gồm các từ theo thứ tự, thay vì độ dài của nó không?

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

Xem các từ như những nút của đồ thị, với một cạnh nối hai từ khác nhau một chữ cái. Mọi cạnh đều có cùng chi phí, vì vậy tìm kiếm theo chiều rộng sẽ tìm ra chuỗi từ ngắn nhất. Phần khó là tìm các cạnh nhanh chóng. Ở dưới đây, n là số từ và L là độ dài của chúng.

Thử từng chiếc thang bằng tìm kiếm theo chiều sâu

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Từ từ hiện tại, hãy thử từng từ chưa dùng cách một ký tự rồi đi sâu hơn, giữ nguyên độ dài khi bạn đến endWord. Đánh dấu các từ trên đường đi là đã dùng, rồi bỏ đánh dấu khi bạn quay lui. Khi đã có một thang gồm best từ, hãy ngừng mở rộng các đường đi có best-1 từ.

Cách này thử mọi thang không lặp lại từ nào, và thang ngắn nhất không bao giờ lặp từ: loại bỏ đoạn nằm giữa hai lần xuất hiện của cùng một từ sẽ rút ngắn thang đó.

26 từ aaa, baa đến zaa đều chỉ cách nhau một ký tự và có thể được sắp xếp theo khoảng 4 × 10^26 cách. Nếu không thể đến được endWord, điều kiện cắt sẽ không bao giờ xảy ra và quá trình tìm kiếm sẽ thử tất cả.

Thuật toán

Đánh dấu đã dùng beginWord nếu từ này có trong danh sách, rồi đặt best thành 0.
search(word, length): tại endWord, giữ lại length nếu giá trị này nhỏ hơn best, rồi trả về. Nếu best đã được đặt và length + 1 ≥ best, hãy trả về.
Nếu không, với mỗi từ chưa dùng chỉ khác một chữ cái, hãy đánh dấu từ đó, gọi search(next, length + 1), rồi bỏ đánh dấu.
Trả về best sau khi gọi search(beginWord, 1).

def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    best = 0  # words in the shortest sequence found so far, 0 while there is none
    used = [word == beginWord for word in wordList]  # words on the current path

    def search(word, length):
        nonlocal best
        if word == endWord:
            if best == 0 or length < best:
                best = length
            return
        if best != 0 and length + 1 >= best:
            return  # any longer path cannot beat the best one
        for i, candidate in enumerate(wordList):
            if not used[i] and one_letter_apart(word, candidate):
                used[i] = True
                search(candidate, length + 1)
                used[i] = False  # free the word for other paths

    search(beginWord, 1)
    return best

Tìm kiếm theo chiều rộng, so sánh mọi cặp

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Hàng đợi duyệt các từ theo thứ tự khoảng cách: mọi từ ở khoảng cách d đều rời hàng đợi trước bất kỳ từ nào ở khoảng cách d + 1. Vì vậy, khi một từ lần đầu được phát hiện ở khoảng cách d, mọi từ gần hơn đều đã được duyệt, và nếu có một chuỗi từ ngắn hơn dẫn đến từ đó thì từ đó đã được phát hiện sớm hơn. Khoảng cách của từ đó được xác định ngay khi nó được thêm vào hàng đợi, vì thế hãy đánh dấu từ đó là đã thăm vào lúc ấy, và lần đầu tiên endWord xuất hiện thì khoảng cách của nó chính là đáp án.

Phiên bản này tìm các từ láng giềng bằng cách so sánh từ đó với mọi từ trong danh sách, rồi dừng khi thấy khác biệt thứ hai: O(n² × L), tối đa 25 triệu lượt so sánh từ với 5,000 từ.

Thuật toán

Nếu endWord không có trong wordList, hãy trả về 0.
Đưa beginWord vào hàng đợi với độ dài 1, đánh dấu là đã thăm nếu từ này có trong danh sách.
Lấy từ tiếp theo và so sánh từ đó với mọi từ chưa được thăm. Với mỗi từ chỉ khác một ký tự: nếu đó là endWord, hãy trả về độ dài + 1; nếu không, hãy đánh dấu từ đó và đưa vào hàng đợi với độ dài + 1.
Nếu hàng đợi trống, hãy trả về 0.

from collections import deque


def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    if endWord not in wordList:
        return 0
    visited = [word == beginWord for word in wordList]
    queue = deque([(beginWord, 1)])  # (word, words in the sequence up to it)
    while queue:
        word, length = queue.popleft()
        # Compare against every word to find the neighbours.
        for i, candidate in enumerate(wordList):
            if not visited[i] and one_letter_apart(word, candidate):
                if candidate == endWord:
                    return length + 1
                visited[i] = True
                queue.append((candidate, length + 1))
    return 0

Tìm kiếm theo chiều rộng với các nhóm ký tự đại diện

Ý tưởng

Hai từ chỉ cách nhau đúng một chữ cái khi ẩn cùng một vị trí sẽ khiến chúng giống nhau: hot và hit đều trở thành h*t. Tạo L mẫu cho mỗi từ, mỗi mẫu ứng với một vị trí bị ẩn, rồi thêm từ đó vào một nhóm cho mỗi mẫu. Các từ láng giềng của một từ là những từ khác nằm trong các nhóm L của nó, được tìm bằng L lần tra cứu bảng băm thay vì duyệt cả danh sách.

Trong ví dụ đầu tiên, l*ad chứa load, còn le*d chứa lend và lewd, nên cấp 2 gồm ba từ đó; tiếp theo, *oad cho ta goad, và go*d cho ta gold ở cấp 4.

Khi đã duyệt một nhóm, mọi từ trong nhóm đều đã được tìm thấy, vì vậy hãy xóa nhóm đó: nhóm 26 từ *aa chỉ được duyệt một lần, không phải 26 lần. Độ phức tạp là O(n × L²) về thời gian và bộ nhớ, khoảng 500.000 bước xử lý chữ cái với 5.000 từ dài 10 chữ cái.

Thuật toán

Nếu endWord không có trong wordList, trả về 0.
Đưa từng từ, bao gồm cả beginWord, vào một nhóm theo từng mẫu L của từ đó.
Đưa beginWord vào hàng đợi, đánh dấu là đã thăm và đặt độ dài là 1.
Với mỗi từ trong một cấp: nếu đó là endWord, trả về độ dài. Nếu không, chuyển mọi từ chưa được thăm trong từng nhóm mẫu của từ đó sang cấp tiếp theo, đánh dấu chúng là đã thăm và làm trống nhóm.
Tăng độ dài thêm 1 sau mỗi cấp. Nếu hàng đợi trống, trả về 0.

from collections import defaultdict, deque


def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    size = len(beginWord)
    # "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
    buckets = defaultdict(list)
    for word in set(wordList) | {beginWord}:
        for i in range(size):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)
    visited = {beginWord}
    queue = deque([beginWord])
    length = 1  # words in the sequence up to the current level
    while queue:
        for _ in range(len(queue)):  # one level: every word at this distance
            word = queue.popleft()
            if word == endWord:
                return length
            for i in range(size):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbour in buckets[pattern]:
                    if neighbour not in visited:
                        visited.add(neighbour)
                        queue.append(neighbour)
                buckets[pattern] = []  # all of them are visited now: never scan it again
        length += 1
    return 0

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

Đếm số lần thay đổi thay vì số từ. Từ lead đến gold cần 3 lần thay đổi và có 4 từ, đáp án là 4.
Bỏ qua bước kiểm tra xem endWord có nằm trong wordList hay không. Ví dụ thứ hai đến được cog, chỉ cách dog một chữ cái, nhưng đáp án là 0.
Đánh dấu một từ đã thăm khi từ đó rời khỏi hàng đợi. Khi đó, một từ trong nhóm *aa có thể được thêm vào tối đa 25 lần, khiến hàng đợi lớn hơn nhiều so với n.
Dùng đệ quy để duyệt theo bậc thang. Một bậc thang ngắn nhất có thể dài hàng nghìn từ, đủ để làm tràn ngăn xếp lời gọi.

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

Độ phức tạp thời gian của Word Ladder là gì?

Với các nhóm ký tự đại diện, độ phức tạp là O(n × L²) với n từ có độ dài L: mỗi từ có L mẫu gồm L chữ cái. So sánh từng cặp từ có độ phức tạp O(n² × L), còn thử mọi chuỗi biến đổi bằng tìm kiếm theo chiều sâu thì có độ phức tạp theo hàm mũ.

Làm thế nào để tìm những từ chỉ khác nhau một chữ cái?

Các nhóm ký tự đại diện là một cách. Cách còn lại là thay từng vị trí bằng từng chữ cái trong số 26 chữ cái, rồi tra kết quả trong tập hợp băm chứa các từ: 26 × L lần tra cứu, mỗi từ có L chữ cái, tổng cộng là O(n × 26 × L²). Cả hai cách đều nhanh hơn việc duyệt qua danh sách.

Liệu BFS hai chiều có thể giúp Word Ladder chạy nhanh hơn không?

Có. Hãy tìm kiếm đồng thời từ cả hai đầu, luôn mở rộng phía nhỏ hơn thêm một mức và dừng lại khi hai phía gặp nhau. Với khoảng b từ lân cận cho mỗi từ và d lần thay đổi, một lượt tìm kiếm có thể chạm đến khoảng b^d từ; hai lượt tìm kiếm gặp nhau ở giữa chỉ chạm đến khoảng 2 × b^(d/2).

def ladderLength(beginWord, endWord, wordList):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

beginWord = "lead"
endWord = "gold"
wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]

Đầu ra mong đợi

Word Ladder

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử từng chiếc thang bằng tìm kiếm theo chiều sâu

Tìm kiếm theo chiều rộng, so sánh mọi cặp

Tìm kiếm theo chiều rộng với các nhóm ký tự đại diện

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

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

Bài tập tương tự