Check if words chain to form a circle
MediumUpdated: Aug 7, 2025
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
Input: ['chair', 'height', 'racket', 'touch', 'tunic']
Output: true
Explanation: The words can form a circle: chair -> racket -> touch -> height -> tunic -> chair
Example 2
Input: ['abc', 'bcd', 'cda']
Output: true
Explanation: The words can form a circle: abc -> bcd -> cda -> abc
Example 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.
Similar Problems
[Reconstruct Itinerary](reconstruct-itinerary) [Course Schedule 1 - Is it Possible](course-schedule-1-is-it-possible) [Course Schedule II](course-schedule-2-get-ordered-courses)
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
C++
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);
}
}
}
};
Go
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)
}
}
}
Java
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);
}
}
}
}
Python
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
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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.