Ghost Word Game Winning Strategy

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

 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
    }
}

 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;
        }
    }
}

 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
        }
    }
}

 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

 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,
        }
    }
}

 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

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Method 1 - Game Theory with Trie and Minimax#

Intuition#

Approach#

Code#

Complexity#