Circular Sentence
EasyPrompt
A sentence is a list of words that are separated by a single space with no leading or trailing spaces.
- For example,
"Hello World","HELLO","hello world hello world"are all sentences.
Words consist of only uppercase and lowercase English letters. Uppercase and lowercase English letters are considered different.
A sentence is circular if:
- The last character of each word in the sentence is equal to the first character of its next word.
- The last character of the last word is equal to the first character of the first word.
For example, "leetcode exercises sound delightful", "eetcode", "leetcode eats soul" are all circular sentences. However, "Leetcode is cool", "happy Leetcode", "Leetcode" and "I like Leetcode" are not circular sentences.
Given a string sentence, return true if it is circular. Otherwise, return false.
Example 1:
Input: sentence = "leetcode exercises sound delightful"
Output: true
Explanation: The words in sentence are ["leetcode", "exercises", "sound", "delightful"].
- leetcode's last character is equal to exercises's first character.
- exercises's last character is equal to sound's first character.
- sound's last character is equal to delightful's first character.
- delightful's last character is equal to leetcode's first character.
The sentence is circular.Example 2:
Input: sentence = "eetcode"
Output: true
Explanation: The words in sentence are ["eetcode"].
- eetcode's last character is equal to eetcode's first character.
The sentence is circular.Example 3:
Input: sentence = "Leetcode is cool"
Output: false
Explanation: The words in sentence are ["Leetcode", "is", "cool"].
- Leetcode's last character is not equal to is's first character.
The sentence is not circular.
Constraints:
1 <= sentence.length <= 500sentenceconsist of only lowercase and uppercase English letters and spaces.- The words in
sentenceare separated by a single space. - There are no leading or trailing spaces.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves breaking the sentence down into individual words and then checking the circular conditions. We first split the input string by spaces to get an array of words. Then, we iterate through this array to verify two conditions: 1) The last character of each word matches the first character of the next word. 2) The last character of the last word matches the first character of the first word.
Algorithm
- Split the
sentencestring by the space character to get an array ofwords. - Let
nbe the number of words. - Check if the first character of
words[0]is different from the last character ofwords[n-1]. If so, returnfalse. - If
nis 1, the previous check is enough, so returntrue. - Iterate with an index
ifrom0ton-2. - In each iteration, check if the last character of
words[i]is different from the first character ofwords[i+1]. If they are different, returnfalse. - If the loop completes without returning, it means all conditions are met. Return
true.
Walkthrough
The algorithm starts by using the split(" ") method to convert the sentence string into an array of strings, where each element is a word.
It then handles the edge case of a sentence with a single word. For a single word, the sentence is circular if its first and last characters are the same.
For sentences with multiple words, it first checks the primary circular condition: if the last character of the last word in the array matches the first character of the first word. If not, it immediately returns false.
Next, it iterates through the array of words from the first word up to the second-to-last word. In each iteration, it compares the last character of the current word with the first character of the next word.
If any of these adjacent word checks fail, the function returns false.
If all checks pass successfully, the function returns true, confirming the sentence is circular.
class Solution { public boolean isCircularSentence(String sentence) { String[] words = sentence.split(" "); int n = words.length; // Check if the last character of the last word matches the first character of the first word. if (words[0].charAt(0) != words[n - 1].charAt(words[n - 1].length() - 1)) { return false; } // If there's only one word, the above check is sufficient. if (n == 1) { return true; } // Check adjacent words. for (int i = 0; i < n - 1; i++) { String currentWord = words[i]; String nextWord = words[i + 1]; if (currentWord.charAt(currentWord.length() - 1) != nextWord.charAt(0)) { return false; } } return true; }}Complexity
Time
O(N), where N is the length of the `sentence`. The `split` operation takes O(N) time. The subsequent loop runs `n-1` times (where `n` is the number of words), which is also proportional to N in the worst case.
Space
O(N), where N is the length of the `sentence`. The `split` method creates a new array of strings, and the total space required to store these strings is proportional to the length of the original sentence.
Trade-offs
Pros
The logic is very clear and directly follows the problem definition.
Easy to implement and debug.
Cons
Uses extra memory to store the array of words, which can be significant for very long sentences.
Solutions
Solution
class Solution {public boolean isCircularSentence(String sentence) { var ss = sentence.split(" "); int n = ss.length; for (int i = 0; i < n; ++i) { if (ss[i].charAt(ss[i].length() - 1) != ss[(i + 1) % n].charAt(0)) { return false; } } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.