Problem#
Ghost is a two-person word game where players alternate appending letters to a word. The first person who spells out a word, or creates a prefix for which there is no possible continuation, loses.
Given a dictionary of words, determine the letters the first player should start with, such that with optimal play they cannot lose.
Examples#
Example 1#
1
2
3
|
Input: dictionary = ["cat", "calf", "dog", "bear"]
Output: ['b']
Explanation: If player 1 starts with 'b', they can force a win. Starting with 'b' leads to "bear" path where player 1 can control the game optimally.
|
Example 2#
1
2
3
|
Input: dictionary = ["a", "ab", "abc"]
Output: []
Explanation: No matter what letter player 1 starts with, player 2 can force them to lose with optimal play.
|
Example 3#
1
2
3
|
Input: dictionary = ["ghost", "ghoul", "go", "good"]
Output: ['g']
Explanation: Starting with 'g' allows player 1 to control the game optimally.
|
Example 4#
1
2
3
|
Input: dictionary = ["cat", "car", "card", "care", "careful"]
Output: ['c']
Explanation: Starting with 'c' gives player 1 a winning strategy.
|
Method 1 - Game Theory with Trie and Minimax#
Intuition#
This is a classic game theory problem. We need to build a trie of all words and then use minimax algorithm to determine winning positions. A position is winning for the current player if they can make a move that puts the opponent in a losing position. A position is losing if all moves lead to winning positions for the opponent.
Approach#
- Build a trie from all dictionary words
- Mark terminal nodes (complete words) in the trie
- Use dynamic programming with game theory:
- A node is losing if it’s a terminal word (current player loses by completing a word)
- A node is losing if it has no children (no valid continuation)
- A node is winning if at least one child leads to a losing position for opponent
- A node is losing if all children lead to winning positions for opponent
- Check all possible starting letters (a-z) to see which ones lead to winning positions
- Return the letters that guarantee a win for player 1
Code#
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
class Solution {
public:
vector<char> ghostGame(vector<string>& dictionary) {
TrieNode* root = buildTrie(dictionary);
computeWinLose(root);
vector<char> ans;
for (int i = 0; i < 26; i++) {
if (root->children[i] && !root->children[i]->isWinning) {
ans.push_back('a' + i);
}
}
return ans;
}
private:
struct TrieNode {
TrieNode* children[26];
bool isWord;
bool isWinning;
TrieNode() : isWord(false), isWinning(false) {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
TrieNode* buildTrie(vector<string>& words) {
TrieNode* root = new TrieNode();
for (string& word : words) {
TrieNode* curr = root;
for (char c : word) {
int idx = c - 'a';
if (!curr->children[idx]) {
curr->children[idx] = new TrieNode();
}
curr = curr->children[idx];
}
curr->isWord = true;
}
return root;
}
void computeWinLose(TrieNode* node) {
if (!node) return;
if (node->isWord) {
node->isWinning = false;
return;
}
bool hasChildren = false;
bool allChildrenWinning = true;
for (int i = 0; i < 26; i++) {
if (node->children[i]) {
hasChildren = true;
computeWinLose(node->children[i]);
if (!node->children[i]->isWinning) {
allChildrenWinning = false;
}
}
}
if (!hasChildren) {
node->isWinning = false;
} else {
node->isWinning = !allChildrenWinning;
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
type TrieNode struct {
children [26]*TrieNode
isWord bool
isWinning bool
}
func ghostGame(dictionary []string) []byte {
root := buildTrie(dictionary)
computeWinLose(root)
var ans []byte
for i := 0; i < 26; i++ {
if root.children[i] != nil && !root.children[i].isWinning {
ans = append(ans, byte('a' + i))
}
}
return ans
}
func buildTrie(words []string) *TrieNode {
root := &TrieNode{}
for _, word := range words {
curr := root
for _, c := range word {
idx := c - 'a'
if curr.children[idx] == nil {
curr.children[idx] = &TrieNode{}
}
curr = curr.children[idx]
}
curr.isWord = true
}
return root
}
func computeWinLose(node *TrieNode) {
if node == nil {
return
}
if node.isWord {
node.isWinning = false
return
}
hasChildren := false
allChildrenWinning := true
for i := 0; i < 26; i++ {
if node.children[i] != nil {
hasChildren = true
computeWinLose(node.children[i])
if !node.children[i].isWinning {
allChildrenWinning = false
}
}
}
if !hasChildren {
node.isWinning = false
} else {
node.isWinning = !allChildrenWinning
}
}
|
Java#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
class Solution {
public List<Character> ghostGame(String[] dictionary) {
TrieNode root = buildTrie(dictionary);
computeWinLose(root);
List<Character> ans = new ArrayList<>();
for (int i = 0; i < 26; i++) {
if (root.children[i] != null && !root.children[i].isWinning) {
ans.add((char)('a' + i));
}
}
return ans;
}
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isWord = false;
boolean isWinning = false;
}
private TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) {
curr.children[idx] = new TrieNode();
}
curr = curr.children[idx];
}
curr.isWord = true;
}
return root;
}
private void computeWinLose(TrieNode node) {
if (node == null) return;
if (node.isWord) {
node.isWinning = false;
return;
}
boolean hasChildren = false;
boolean allChildrenWinning = true;
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
hasChildren = true;
computeWinLose(node.children[i]);
if (!node.children[i].isWinning) {
allChildrenWinning = false;
}
}
}
if (!hasChildren) {
node.isWinning = false;
} else {
node.isWinning = !allChildrenWinning;
}
}
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
class Solution {
fun ghostGame(dictionary: Array<String>): List<Char> {
val root = buildTrie(dictionary)
computeWinLose(root)
val ans = mutableListOf<Char>()
for (i in 0..25) {
if (root.children[i] != null && !root.children[i]!!.isWinning) {
ans.add('a' + i)
}
}
return ans
}
class TrieNode {
val children = Array<TrieNode?>(26) { null }
var isWord = false
var isWinning = false
}
private fun buildTrie(words: Array<String>): TrieNode {
val root = TrieNode()
for (word in words) {
var curr = root
for (c in word) {
val idx = c - 'a'
if (curr.children[idx] == null) {
curr.children[idx] = TrieNode()
}
curr = curr.children[idx]!!
}
curr.isWord = true
}
return root
}
private fun computeWinLose(node: TrieNode?) {
if (node == null) return
if (node.isWord) {
node.isWinning = false
return
}
var hasChildren = false
var allChildrenWinning = true
for (i in 0..25) {
if (node.children[i] != null) {
hasChildren = true
computeWinLose(node.children[i])
if (!node.children[i]!!.isWinning) {
allChildrenWinning = false
}
}
}
if (!hasChildren) {
node.isWinning = false
} else {
node.isWinning = !allChildrenWinning
}
}
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
class Solution:
def ghostGame(self, dictionary: List[str]) -> List[str]:
root = self.buildTrie(dictionary)
self.computeWinLose(root)
ans = []
for i in range(26):
if root.children[i] and not root.children[i].isWinning:
ans.append(chr(ord('a') + i))
return ans
class TrieNode:
def __init__(self):
self.children = [None] * 26
self.isWord = False
self.isWinning = False
def buildTrie(self, words: List[str]) -> 'TrieNode':
root = self.TrieNode()
for word in words:
curr = root
for c in word:
idx = ord(c) - ord('a')
if not curr.children[idx]:
curr.children[idx] = self.TrieNode()
curr = curr.children[idx]
curr.isWord = True
return root
def computeWinLose(self, node: 'TrieNode') -> None:
if not node:
return
if node.isWord:
node.isWinning = False
return
hasChildren = False
allChildrenWinning = True
for i in range(26):
if node.children[i]:
hasChildren = True
self.computeWinLose(node.children[i])
if not node.children[i].isWinning:
allChildrenWinning = False
if not hasChildren:
node.isWinning = False
else:
node.isWinning = not allChildrenWinning
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
impl Solution {
pub fn ghost_game(dictionary: Vec<String>) -> Vec<char> {
let mut root = Self::build_trie(&dictionary);
Self::compute_win_lose(&mut root);
let mut ans = Vec::new();
for i in 0..26 {
if let Some(child) = &root.children[i] {
if !child.is_winning {
ans.push((b'a' + i as u8) as char);
}
}
}
ans
}
fn build_trie(words: &Vec<String>) -> TrieNode {
let mut root = TrieNode::new();
for word in words {
let mut curr = &mut root;
for c in word.chars() {
let idx = (c as u8 - b'a') as usize;
if curr.children[idx].is_none() {
curr.children[idx] = Some(Box::new(TrieNode::new()));
}
curr = curr.children[idx].as_mut().unwrap();
}
curr.is_word = true;
}
root
}
fn compute_win_lose(node: &mut TrieNode) {
if node.is_word {
node.is_winning = false;
return;
}
let mut has_children = false;
let mut all_children_winning = true;
for i in 0..26 {
if let Some(child) = &mut node.children[i] {
has_children = true;
Self::compute_win_lose(child);
if !child.is_winning {
all_children_winning = false;
}
}
}
if !has_children {
node.is_winning = false;
} else {
node.is_winning = !all_children_winning;
}
}
}
struct TrieNode {
children: [Option<Box<TrieNode>>; 26],
is_word: bool,
is_winning: bool,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: Default::default(),
is_word: false,
is_winning: false,
}
}
}
|
TypeScript#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
class Solution {
ghostGame(dictionary: string[]): string[] {
const root = this.buildTrie(dictionary);
this.computeWinLose(root);
const ans: string[] = [];
for (let i = 0; i < 26; i++) {
if (root.children[i] && !root.children[i]!.isWinning) {
ans.push(String.fromCharCode('a'.charCodeAt(0) + i));
}
}
return ans;
}
private buildTrie(words: string[]): TrieNode {
const root = new TrieNode();
for (const word of words) {
let curr = root;
for (const c of word) {
const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
if (!curr.children[idx]) {
curr.children[idx] = new TrieNode();
}
curr = curr.children[idx]!;
}
curr.isWord = true;
}
return root;
}
private computeWinLose(node: TrieNode | null): void {
if (!node) return;
if (node.isWord) {
node.isWinning = false;
return;
}
let hasChildren = false;
let allChildrenWinning = true;
for (let i = 0; i < 26; i++) {
if (node.children[i]) {
hasChildren = true;
this.computeWinLose(node.children[i]);
if (!node.children[i]!.isWinning) {
allChildrenWinning = false;
}
}
}
if (!hasChildren) {
node.isWinning = false;
} else {
node.isWinning = !allChildrenWinning;
}
}
}
class TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
isWord: boolean = false;
isWinning: boolean = false;
}
|
Complexity#
- ⏰ Time complexity:
O(N * M + 26 * T), where N is the number of words, M is the average word length for building the trie, and T is the number of trie nodes for computing win/lose states
- 🧺 Space complexity:
O(T), where T is the total number of nodes in the trie, which can be up to N * M in the worst case