Đề bài
Language models work with tokens, not raw text. A simple tokenizer lowercases the text and treats every run of letters a-z and digits 0-9 as a word; everything else (spaces, punctuation, other characters) separates words.
Build the vocabulary: the distinct words, sorted by how often they appear (most frequent first), with ties broken alphabetically. A word's position in this list is its token ID.
Implement build_vocabulary(text).
Input
text: Any text.
Output
Return the vocabulary as a list of words. Return an empty list if the text has no words.
Ràng buộc
0 ≤ length of text ≤ 100,000
Ví dụ
Đầu vào:
text = "The cat sat on the mat. The end!"
Kết quả mong đợi:
expected = ["the", "cat", "end", "mat", "on", "sat"]
Đầu vào:
std::string text = "The cat sat on the mat. The end!";
Kết quả mong đợi:
std::vector<std::string> expected = {"the", "cat", "end", "mat", "on", "sat"};
Đầu vào:
string text = "The cat sat on the mat. The end!";
Kết quả mong đợi:
string[] expected = new string[] {"the", "cat", "end", "mat", "on", "sat"};
Giải thích
Lowercased, the words are the, cat, sat, on, the, mat, the, end. "the" appears 3 times; the rest appear once and are sorted alphabetically: ["the", "cat", "end", "mat", "on", "sat"].
Đầu vào:
text = "AI, ai and A.I. (2024)"
Kết quả mong đợi:
expected = ["ai", "2024", "a", "and", "i"]
Đầu vào:
std::string text = "AI, ai and A.I. (2024)";
Kết quả mong đợi:
std::vector<std::string> expected = {"ai", "2024", "a", "and", "i"};
Đầu vào:
string text = "AI, ai and A.I. (2024)";
Kết quả mong đợi:
string[] expected = new string[] {"ai", "2024", "a", "and", "i"};
Giải thích
Words: ai, ai, and, a, i, 2024. "ai" appears twice; the others once, sorted alphabetically with digits before letters: ["ai", "2024", "a", "and", "i"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
First extract only runs of letters and digits, lowercased, and ignore every other character.
Gợi ý 2
Count how often each word appears, then sort by frequency descending and alphabetically for ties.
Gợi ý 3
If the text contains no valid words, return an empty list instead of a singleton or null result.
Độ phức tạp mong đợi
O(n log k) time, O(k) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.