Check if words chain to form a circle

Problem

Given a list of words, determine whether the words can be chained to form a circle. A word X can be placed in front of another word Y in a circle if the last character of X is same as the first character of Y.

Examples

Example 1

1
2
3


Input: ['chair', 'height', 'racket', 'touch', 'tunic']
Output: true
Explanation: The words can form a circle: chair -> racket -> touch -> height -> tunic -> chair

Example 2

1
2
3


Input: ['abc', 'bcd', 'cda']
Output: true
Explanation: The words can form a circle: abc -> bcd -> cda -> abc

Example 3

1
2
3


Input: ['hello', 'world']
Output: false
Explanation: 'hello' ends with 'o' and 'world' starts with 'w', 'world' ends with 'd' and 'hello' starts with 'h'. No valid circle can be formed.

Solution

Method 1 – Eulerian Circuit Detection

Intuition

This problem can be modeled as finding an Eulerian circuit in a directed graph. Each word represents a directed edge from its first character to its last character. An Eulerian circuit exists if and only if the graph is strongly connected and every vertex has equal in-degree and out-degree.

Approach

Build a directed graph where each character is a vertex and each word represents an edge from the first character to the last character.
Count the in-degree and out-degree for each character.
Check if all vertices with non-zero degree have equal in-degree and out-degree.
Check if the graph formed by the words is strongly connected (all vertices with edges should be reachable from each other).
If both conditions are satisfied, the words can form a circle.

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
73
74
75
76


class Solution {
public:
    bool canFormCircle(vector<string>& words) {
        vector<int> in(26, 0), out(26, 0);
        vector<vector<bool>> graph(26, vector<bool>(26, false));
        vector<bool> mark(26, false);
        
        for (string& word : words) {
            int first = word[0] - 'a';
            int last = word.back() - 'a';
            out[first]++;
            in[last]++;
            graph[first][last] = true;
            mark[first] = mark[last] = true;
        }
        
        // Check in-degree equals out-degree
        for (int i = 0; i < 26; i++) {
            if (in[i] != out[i]) return false;
        }
        
        // Check strong connectivity using DFS
        return isStronglyConnected(graph, mark);
    }
    
private:
    bool isStronglyConnected(vector<vector<bool>>& graph, vector<bool>& mark) {
        // Find first marked vertex
        int start = -1;
        for (int i = 0; i < 26; i++) {
            if (mark[i]) {
                start = i;
                break;
            }
        }
        
        if (start == -1) return true;
        
        // DFS from start vertex
        vector<bool> visited(26, false);
        dfs(graph, start, visited);
        
        // Check if all marked vertices are visited
        for (int i = 0; i < 26; i++) {
            if (mark[i] && !visited[i]) return false;
        }
        
        // Create transpose graph
        vector<vector<bool>> transpose(26, vector<bool>(26, false));
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                transpose[j][i] = graph[i][j];
            }
        }
        
        // DFS on transpose
        fill(visited.begin(), visited.end(), false);
        dfs(transpose, start, visited);
        
        // Check if all marked vertices are visited in transpose
        for (int i = 0; i < 26; i++) {
            if (mark[i] && !visited[i]) return false;
        }
        
        return true;
    }
    
    void dfs(vector<vector<bool>>& graph, int v, vector<bool>& visited) {
        visited[v] = true;
        for (int i = 0; i < 26; i++) {
            if (graph[v][i] && !visited[i]) {
                dfs(graph, i, visited);
            }
        }
    }
};

 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89


func canFormCircle(words []string) bool {
    in := make([]int, 26)
    out := make([]int, 26)
    graph := make([][]bool, 26)
    for i := range graph {
        graph[i] = make([]bool, 26)
    }
    mark := make([]bool, 26)
    
    for _, word := range words {
        first := int(word[0] - 'a')
        last := int(word[len(word)-1] - 'a')
        out[first]++
        in[last]++
        graph[first][last] = true
        mark[first] = true
        mark[last] = true
    }
    
    // Check in-degree equals out-degree
    for i := 0; i < 26; i++ {
        if in[i] != out[i] {
            return false
        }
    }
    
    return isStronglyConnected(graph, mark)
}

func isStronglyConnected(graph [][]bool, mark []bool) bool {
    // Find first marked vertex
    start := -1
    for i := 0; i < 26; i++ {
        if mark[i] {
            start = i
            break
        }
    }
    
    if start == -1 {
        return true
    }
    
    // DFS from start vertex
    visited := make([]bool, 26)
    dfs(graph, start, visited)
    
    // Check if all marked vertices are visited
    for i := 0; i < 26; i++ {
        if mark[i] && !visited[i] {
            return false
        }
    }
    
    // Create transpose graph
    transpose := make([][]bool, 26)
    for i := range transpose {
        transpose[i] = make([]bool, 26)
    }
    for i := 0; i < 26; i++ {
        for j := 0; j < 26; j++ {
            transpose[j][i] = graph[i][j]
        }
    }
    
    // DFS on transpose
    for i := range visited {
        visited[i] = false
    }
    dfs(transpose, start, visited)
    
    // Check if all marked vertices are visited in transpose
    for i := 0; i < 26; i++ {
        if mark[i] && !visited[i] {
            return false
        }
    }
    
    return true
}

func dfs(graph [][]bool, v int, visited []bool) {
    visited[v] = true
    for i := 0; i < 26; i++ {
        if graph[v][i] && !visited[i] {
            dfs(graph, i, visited)
        }
    }
}

 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


class Solution {
    public boolean canFormCircle(String[] words) {
        int[] in = new int[26];
        int[] out = new int[26];
        boolean[][] graph = new boolean[26][26];
        boolean[] mark = new boolean[26];
        
        for (String word : words) {
            int first = word.charAt(0) - 'a';
            int last = word.charAt(word.length() - 1) - 'a';
            out[first]++;
            in[last]++;
            graph[first][last] = true;
            mark[first] = mark[last] = true;
        }
        
        // Check in-degree equals out-degree
        for (int i = 0; i < 26; i++) {
            if (in[i] != out[i]) return false;
        }
        
        return isStronglyConnected(graph, mark);
    }
    
    private boolean isStronglyConnected(boolean[][] graph, boolean[] mark) {
        // Find first marked vertex
        int start = -1;
        for (int i = 0; i < 26; i++) {
            if (mark[i]) {
                start = i;
                break;
            }
        }
        
        if (start == -1) return true;
        
        // DFS from start vertex
        boolean[] visited = new boolean[26];
        dfs(graph, start, visited);
        
        // Check if all marked vertices are visited
        for (int i = 0; i < 26; i++) {
            if (mark[i] && !visited[i]) return false;
        }
        
        // Create transpose graph
        boolean[][] transpose = new boolean[26][26];
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                transpose[j][i] = graph[i][j];
            }
        }
        
        // DFS on transpose
        Arrays.fill(visited, false);
        dfs(transpose, start, visited);
        
        // Check if all marked vertices are visited in transpose
        for (int i = 0; i < 26; i++) {
            if (mark[i] && !visited[i]) return false;
        }
        
        return true;
    }
    
    private void dfs(boolean[][] graph, int v, boolean[] visited) {
        visited[v] = true;
        for (int i = 0; i < 26; i++) {
            if (graph[v][i] && !visited[i]) {
                dfs(graph, i, visited);
            }
        }
    }
}

 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:
    def can_form_circle(self, words: list[str]) -> bool:
        in_degree = [0] * 26
        out_degree = [0] * 26
        graph = [[False] * 26 for _ in range(26)]
        mark = [False] * 26
        
        for word in words:
            first = ord(word[0]) - ord('a')
            last = ord(word[-1]) - ord('a')
            out_degree[first] += 1
            in_degree[last] += 1
            graph[first][last] = True
            mark[first] = mark[last] = True
        
        # Check in-degree equals out-degree
        for i in range(26):
            if in_degree[i] != out_degree[i]:
                return False
        
        return self._is_strongly_connected(graph, mark)
    
    def _is_strongly_connected(self, graph: list[list[bool]], mark: list[bool]) -> bool:
        # Find first marked vertex
        start = -1
        for i in range(26):
            if mark[i]:
                start = i
                break
        
        if start == -1:
            return True
        
        # DFS from start vertex
        visited = [False] * 26
        self._dfs(graph, start, visited)
        
        # Check if all marked vertices are visited
        for i in range(26):
            if mark[i] and not visited[i]:
                return False
        
        # Create transpose graph
        transpose = [[False] * 26 for _ in range(26)]
        for i in range(26):
            for j in range(26):
                transpose[j][i] = graph[i][j]
        
        # DFS on transpose
        visited = [False] * 26
        self._dfs(transpose, start, visited)
        
        # Check if all marked vertices are visited in transpose
        for i in range(26):
            if mark[i] and not visited[i]:
                return False
        
        return True
    
    def _dfs(self, graph: list[list[bool]], v: int, visited: list[bool]) -> None:
        visited[v] = True
        for i in range(26):
            if graph[v][i] and not visited[i]:
                self._dfs(graph, i, visited)

Complexity

⏰ Time complexity: O(V + E), where V is the number of unique characters (at most 26) and E is the number of words. We perform DFS twice on the graph.
🧺 Space complexity: O(V²), for storing the adjacency matrix and visited arrays, where V is at most 26.

Method 2 – Backtracking with Path Finding

Intuition

We can solve this problem using backtracking by trying to build a valid chain that uses all words exactly once and forms a circle. This approach directly simulates the process of forming a chain.

Approach

Start with any word and try to build a chain by finding words whose first character matches the last character of the current word.
Use backtracking to try all possible combinations.
Keep track of used words to ensure each word is used exactly once.
Check if we can return to the starting word after using all words.

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


class Solution {
public:
    bool canFormCircle(vector<string>& words) {
        int n = words.size();
        if (n == 0) return true;
        if (n == 1) return words[0][0] == words[0].back();
        
        vector<bool> used(n, false);
        
        for (int i = 0; i < n; i++) {
            used[i] = true;
            if (backtrack(words, used, words[i][0], words[i].back(), 1, n)) {
                return true;
            }
            used[i] = false;
        }
        
        return false;
    }
    
private:
    bool backtrack(vector<string>& words, vector<bool>& used, char start, char curr, int count, int total) {
        if (count == total) {
            return curr == start;
        }
        
        for (int i = 0; i < words.size(); i++) {
            if (!used[i] && words[i][0] == curr) {
                used[i] = true;
                if (backtrack(words, used, start, words[i].back(), count + 1, total)) {
                    return true;
                }
                used[i] = false;
            }
        }
        
        return 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


func canFormCircle(words []string) bool {
    n := len(words)
    if n == 0 {
        return true
    }
    if n == 1 {
        return words[0][0] == words[0][len(words[0])-1]
    }
    
    used := make([]bool, n)
    
    for i := 0; i < n; i++ {
        used[i] = true
        if backtrack(words, used, words[i][0], words[i][len(words[i])-1], 1, n) {
            return true
        }
        used[i] = false
    }
    
    return false
}

func backtrack(words []string, used []bool, start byte, curr byte, count int, total int) bool {
    if count == total {
        return curr == start
    }
    
    for i := 0; i < len(words); i++ {
        if !used[i] && words[i][0] == curr {
            used[i] = true
            if backtrack(words, used, start, words[i][len(words[i])-1], count+1, total) {
                return true
            }
            used[i] = false
        }
    }
    
    return 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


class Solution {
    public boolean canFormCircle(String[] words) {
        int n = words.length;
        if (n == 0) return true;
        if (n == 1) return words[0].charAt(0) == words[0].charAt(words[0].length() - 1);
        
        boolean[] used = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            used[i] = true;
            if (backtrack(words, used, words[i].charAt(0), words[i].charAt(words[i].length() - 1), 1, n)) {
                return true;
            }
            used[i] = false;
        }
        
        return false;
    }
    
    private boolean backtrack(String[] words, boolean[] used, char start, char curr, int count, int total) {
        if (count == total) {
            return curr == start;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (!used[i] && words[i].charAt(0) == curr) {
                used[i] = true;
                if (backtrack(words, used, start, words[i].charAt(words[i].length() - 1), count + 1, total)) {
                    return true;
                }
                used[i] = false;
            }
        }
        
        return 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


class Solution:
    def can_form_circle(self, words: list[str]) -> bool:
        n = len(words)
        if n == 0:
            return True
        if n == 1:
            return words[0][0] == words[0][-1]
        
        used = [False] * n
        
        for i in range(n):
            used[i] = True
            if self._backtrack(words, used, words[i][0], words[i][-1], 1, n):
                return True
            used[i] = False
        
        return False
    
    def _backtrack(self, words: list[str], used: list[bool], start: str, curr: str, count: int, total: int) -> bool:
        if count == total:
            return curr == start
        
        for i in range(len(words)):
            if not used[i] and words[i][0] == curr:
                used[i] = True
                if self._backtrack(words, used, start, words[i][-1], count + 1, total):
                    return True
                used[i] = False
        
        return False

Complexity

⏰ Time complexity: O(n!), where n is the number of words. In the worst case, we might need to try all permutations of words.
🧺 Space complexity: O(n), for the recursion stack and the used array.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Similar Problems#

Solution#

Method 1 – Eulerian Circuit Detection#

Intuition#

Approach#

Code#

Complexity#

Method 2 – Backtracking with Path Finding#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Example 3

Similar Problems

Solution

Method 1 – Eulerian Circuit Detection

Intuition

Approach

Code

Complexity

Method 2 – Backtracking with Path Finding

Intuition

Approach

Code

Complexity