Tách từ hợp lệ theo từ điển (Word Break) | Đấu Trường Thuật Toán

Cho một chuỗi ký tự s và một mảng danh sách từ điển wordDict chứa các từ duy nhất.

Hãy xác định xem có thể phân tách s thành một chuỗi các từ liên tiếp có nghĩa, trong đó mỗi từ đều nằm trong từ điển wordDict hay không.

Lưu ý: Các từ trong từ điển có thể được tái sử dụng nhiều lần trong quá trình phân tách.

Ví dụ 1:

Input:
s = 'leetcode'
wordDict = ['leet', 'code']
Output: true
Giải thích: 'leetcode' có thể tách thành 'leet code'.

Ví dụ 2:

Input:
s = 'applepenapple'
wordDict = ['apple', 'pen']
Output: true
Giải thích: 'applepenapple' = 'apple pen apple'.

Ví dụ 3:

Input:
s = 'catsandog'
wordDict = ['cats', 'dog', 'sand', 'and', 'cat']
Output: false

Định Dạng Đầu Vào (Input)

Dòng 1: Chuỗi s
Dòng 2: Mảng các từ wordDict

Định Dạng Đầu Ra (Output)

true hoặc false

Ràng Buộc (Constraints)

1 <= s.length <= 300
1 <= wordDict.length <= 1000

Ví Dụ Kiểm Thử Mẫu

Ví dụ 1:

Input:

"leetcode"
["leet", "code"]

Output:

true

Giải thích: leet + code

Ví dụ 2:

Input:

"applepenapple"
["apple", "pen"]

Output:

true

Giải thích: apple + pen + apple

Ví dụ 3:

Input:

"catsandog"
["cats", "dog", "sand", "and", "cat"]

Output:

false

Giải thích: Không thể ghép thành công

Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.

Quy Hoạch Động Tiền Tố O(n^2)

Gọi dp[i] là true nếu chuỗi tiền tố s[0..i] có thể tách từ hợp lệ.
dp[i] = true nếu tồn tại j < i sao cho dp[j] == true và s[j..i] in wordDict.

Vui lòng đăng nhập

Đăng nhập tài khoản học viên để xem lịch sử nộp bài của bạn.

Đăng nhập