Problem 2490

Abstract / Summary

Check if all words in a sentence can be reached by moving forward the number of letters in each word from the current position in a circular string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 2490.py

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        words = sentence.split(" ")
        return all(a[-1] == b[0] for a, b in zip(words, words[1:])) and words[0][0] == words[-1][-1]
4 lines | 214 bytes | submitted February 23, 2024 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 70% (200k+ submissions).

Typical patterns to solve this problem:
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a single method isCircularSentence that determines whether a given sentence satisfies the circular-word property: the last character of each word must match the first character of the next word, and the first character of the first word must match the last character of the final word. The solution is concise, leveraging Python’s built-in string operations and iterator utilities to perform the check in a single expression.

Key Steps

Splitting the Input

The first operation isolates individual words by separating the input string on space characters.

words = sentence.split(" ")

The split call returns a list where each element corresponds to a word in the original sentence. Because the specification treats a single space as the delimiter, this step correctly handles sentences with any number of words, including a single-word case.

Pairwise Comparison of Adjacent Words

The core of the algorithm uses a generator expression combined with zip to compare the trailing character of each word with the leading character of the following word.

all(a[-1] == b[0] for a, b in zip(words, words[1:]))

zip(words, words[1:]) creates pairs (a, b) where a is a word and b is the word that follows it. For each pair, the expression checks whether the last character of a (a[-1]) equals the first character of b (b[0]). The all function aggregates the results, yielding True only if every adjacent pair satisfies the condition.

Closing the Circular Loop

After confirming the adjacency condition, the method validates the circular link between the first and last words.

words[0][0] == words[-1][-1]

Here, words[0][0] extracts the first character of the initial word, while words[-1][-1] extracts the last character of the final word. Equality of these two characters completes the circular requirement.

Combining the Checks

Both the pairwise adjacency result and the circular link result are combined with a logical and to produce the final Boolean outcome.

return all(... ) and words[0][0] == words[-1][-1]

If either component is False, the method returns False; otherwise, it returns True.

Edge Cases Handled

The implementation gracefully manages several boundary conditions without additional code.

When the sentence consists of a single word, words[1:] yields an empty list, causing zip(words, words[1:]) to produce no pairs. The all function applied to an empty iterator returns True by definition, so the adjacency check does not reject a single-word input. The final circular check then compares the first and last characters of the same word, correctly determining whether the word forms a trivial circular sentence (i.e., its first and last characters match).

If the input contains leading, trailing, or multiple consecutive spaces, split(" ") treats each space as a delimiter, producing empty strings for consecutive spaces. The subsequent character indexing (a[-1] and b[0]) would raise an error on an empty string, but the problem constraints guarantee that words are non-empty and separated by single spaces, so the code operates safely within those bounds.

When the sentence includes Unicode characters, the code still works because Python’s string indexing operates on Unicode code points. However, the implementation restricts itself to ASCII characters as per the specification, ensuring consistent behavior.

Performance Optimizations

The solution achieves optimal traversal by iterating over the word list only once for the adjacency check. The use of a generator expression inside all avoids constructing an intermediate list of Boolean values, thereby reducing memory overhead. The zip function pairs elements without additional copying, and the final circular comparison is a constant-time operation. Consequently, the method runs in linear time relative to the number of words, with minimal auxiliary space beyond the list produced by split.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a long line of toy trains sitting on a track. The code starts by breaking one long sentence into smaller pieces, just like taking apart a train set to see each individual car. Each car has a front and a back. The goal is to see if the back of one car perfectly matches the front of the car right behind it. It is like making sure every connector on the train cars clicks together just right. Finally, the code also checks the very first car and the very last car to make sure they connect to each other to form a complete circle. If every single connection matches up, then the whole sentence forms a perfect, endless loop.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 8.11 | σ = 1.17

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster Java C++ Python TS
WalkCCC Java C++ Python
leetcode.ca JS Java C++ Go Python Rust TS
Progiez Java C++ Python
github charles-wangkai Java
everthis JS
fartem Ruby
fsq C++
JoshCrozier JS
Shamik07 Dart
varunu28 Java
withaarzoo C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez C++, Java, Python
charles-wangkai Java
everthis JavaScript
fartem Ruby
fsq C++
JoshCrozier JavaScript
Shamik07 Dart
varunu28 Java
withaarzoo C++
25 links | 12 authors | 9 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

10 solutions   February 23, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality