Circular Sentence Problem

Problem

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 a word is equal to the first character of the 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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5

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:

1
2
3
4
5

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.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Splitting the string

To determine if a sentence is circular, we can follow these steps:

1. Split the sentence into words based on spaces.
2. Check if each word’s last character matches the first character of the next word.
3. Additionally, ensure that the last word’s last character matches the first word’s first character.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
    public boolean isCircularSentence(String sentence) {
        String[] words = sentence.split(" ");
        int k = words.length;
        
        for (int i = 0; i < k; i++) {
            String currWord = words[i];
            String nextWord = words[(i + 1) % k];
            
            if (currWord.charAt(currWord.length() - 1) != nextWord.charAt(0)) {
                return false;
            }
        }
        
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        words: List[str] = sentence.split(' ')
        n: int = len(words)
        
        for i in range(n):
            current_word = words[i]
            next_word = words[(i + 1) % n]
            
            if current_word[-1] != next_word[0]:
                return False
        
        return True

Complexity

• ⏰ Time complexity: O(n), where n is the length of the sentence. This is because we need to iterate through the split words to check their characters.
• 🧺 Space complexity: O(n) as we are splitting the string into k words and storing them in array.

Method 2 - Simple Iteration char by char

If we don’t split the string, we can directly iterate through its characters and perform checks as follows:

• Whenever a space (’ ‘) is encountered, ensure the character before the space matches the character after the space.
• If any mismatch is found, return false.

Additionally, we need to match the first and last characters of the sentence. Here is the refined approach:

1. Initial Check: Ensure the first character of the sentence matches the last character.
2. Traverse Sentence: Iterate through the sentence from the second character to the second-last character.
   • Whenever a space (’ ‘) is encountered, check if the character immediately before the space matches the character immediately after the space.
   • If a mismatch is found at any point, return false.
3. Final Check: If all conditions during traversal are satisfied, return true.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public boolean isCircularSentence(String sentence) {
        int n = sentence.length();
        
        if (n == 0 || sentence.charAt(0) != sentence.charAt(n - 1)) {
            return false;
        }
        
        for (int i = 1; i < n - 1; i++) {
            if (sentence.charAt(i) == ' ') {
                if (sentence.charAt(i - 1) != sentence.charAt(i + 1)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        n: int = len(sentence)
        
        if n == 0 or sentence[0] != sentence[-1]:
            return False
        
        for i in range(1, n - 1):
            if sentence[i] == ' ':
                if sentence[i - 1] != sentence[i + 1]:
                    return False
        
        return True

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)