Circular Sentence

#874 Most AskedEasy

Circular Sentence #874 Most Asked

Easy

Bloomberg LP

2 views

Topics:

Strings

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 <= 500
sentence consist of only lowercase and uppercase English letters and spaces.
The words in sentence are separated by a single space.
There are no leading or trailing spaces.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input sentence be empty or null?
Are the words in the sentence guaranteed to contain at least one character?
Is the sentence guaranteed to have at least two words, or could it have only one word?
Are we case-sensitive? Should I treat 'A' and 'a' as different characters?
Besides spaces, can the input sentence contain any other non-alphanumeric characters?

Brute Force Solution

Approach

The brute force method for the circular sentence problem involves checking if the first letter of each word matches the last letter of the previous word, going all the way around. It makes sure that for every adjacent pair of words, this property holds true. It's like meticulously checking every link in a chain to see if it connects properly.

Here's how the algorithm would work step-by-step:

Take the sentence and split it up into individual words.
Check if the first letter of the second word matches the last letter of the first word.
Then, check if the first letter of the third word matches the last letter of the second word.
Continue this process for all consecutive pairs of words in the sentence.
Finally, check if the first letter of the very first word matches the last letter of the very last word.
If all these checks pass, then the sentence is circular; otherwise, it is not.

Code Implementation

def is_circular_sentence(sentence):
    words = sentence.split()

    # Handle edge case of empty sentence
    if not words:
        return True

    number_of_words = len(words)

    # Iterate through words checking first and last letters
    for i in range(number_of_words - 1):
        current_word = words[i]
        next_word = words[i + 1]

        # Check if the last letter of current word matches the first letter of next word
        if current_word[-1] != next_word[0]:
            return False

    # Check if last word connects back to first word
    if words[-1][-1] != words[0][0]:
        return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm splits the sentence into n words, where n is the number of words in the sentence. The core of the algorithm iterates through the list of words once to check if the last letter of one word matches the first letter of the next. Additionally, there is a single check to compare the first and last words. Therefore, the dominant operation is the single pass through the n words, resulting in O(n) time complexity, as the number of operations grows linearly with the number of words.

Space Complexity

O(N) – The dominant space complexity comes from splitting the input sentence into a list of words. In the worst-case scenario, each word could be a single character separated by spaces, resulting in a list of N words where N is the length of the input string. This list of words is stored in memory as an auxiliary data structure. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The key is to check if the first letter of each word matches the last letter of the preceding word. If the sentence is made of only one word, verify the first and last letter of the word are the same. This approach quickly verifies the circular property by focusing on adjacent word pairings.

Here's how the algorithm would work step-by-step:

First, split the input sentence into individual words.
Next, if there is only one word in the sentence, check if the first and last character are the same, and return whether or not this is the case.
Otherwise, start with the first word in the sentence.
Compare the last letter of the current word with the first letter of the next word.
Continue this comparison for all consecutive pairs of words in the sentence.
Also, check if the last letter of the final word matches the first letter of the first word in the sentence.
If all adjacent word pairs meet this letter-matching criteria, the sentence is circular and return true. Otherwise, return false.

Code Implementation

def is_circular_sentence(sentence):
    words = sentence.split()

    # Handle the base case of a single-word sentence
    if len(words) == 1:
        return words[0][0] == words[0][-1]

    # Check if the last letter of the last word matches the first letter of the first word
    if words[-1][-1] != words[0][0]:
        return False

    # Iterate through the words to check if adjacent words form a cycle
    for word_index in range(len(words) - 1):
        current_word = words[word_index]
        next_word = words[word_index + 1]

        # If the last character of the current word
        # does not equal the first character of the next
        if current_word[-1] != next_word[0]:
            return False

        #Check that adjacent words connect

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm first splits the sentence into words, which takes O(n) time where n is the number of characters in the sentence. Then, it iterates through the words once to check the first and last characters of adjacent words. This iteration involves a fixed number of operations for each word. Finally, the algorithm checks the last word against the first word, which is a constant time operation. Therefore, the overall time complexity is dominated by the initial split and the single iteration through the words, resulting in O(n).

Space Complexity

O(N) – The primary auxiliary space usage comes from splitting the input sentence into individual words, creating a list of words. In the worst case, the sentence could consist of N words, where N is the number of words in the input sentence, thus the array of the words would take O(N) space. The other variables used for comparisons take constant space and can be ignored compared to the space used for the list of words. Thus, the overall space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty sentence	Return true if the sentence is null or empty, as it vacuously satisfies the circular condition.
Sentence with only one word	Return true if the sentence has only one word because the last character is the same as the first.
Sentence with two words where the last character of the first word doesn't match the first character of the second word	Return false because the basic circular requirement is not met.
Sentence with two words where the last character of the second word doesn't match the first character of the first word	Return false because the basic circular requirement is not met.
Sentence with leading/trailing spaces or multiple spaces between words	The solution should trim leading/trailing spaces and split on single spaces only.
Sentence with mixed-case letters	The comparison of first and last letters must be case-insensitive.
Very long sentence (performance)	The solution should iterate linearly through the words, so long sentences should not cause performance issues.
Sentence containing non-alphabetic characters	The problem statement specifies only uppercase and lowercase letters are allowed, so either throw an error or assume that the code must compare alphanumeric characters and skip over non-alphanumeric ones.

Null or empty sentence

How to Handle:

Return true if the sentence is null or empty, as it vacuously satisfies the circular condition.

Sentence with only one word

How to Handle:

Return true if the sentence has only one word because the last character is the same as the first.

Sentence with two words where the last character of the first word doesn't match the first character of the second word

How to Handle:

Return false because the basic circular requirement is not met.

Sentence with two words where the last character of the second word doesn't match the first character of the first word

How to Handle:

Return false because the basic circular requirement is not met.

Sentence with leading/trailing spaces or multiple spaces between words

How to Handle:

The solution should trim leading/trailing spaces and split on single spaces only.

Sentence with mixed-case letters

How to Handle:

The comparison of first and last letters must be case-insensitive.

Very long sentence (performance)

How to Handle:

The solution should iterate linearly through the words, so long sentences should not cause performance issues.

Sentence containing non-alphabetic characters

How to Handle:

The problem statement specifies only uppercase and lowercase letters are allowed, so either throw an error or assume that the code must compare alphanumeric characters and skip over non-alphanumeric ones.