Leetcode 2490: Circular Sentence

Input: The input is a string, where words are separated by spaces and consist of only uppercase and lowercase English letters.

Example: sentence = 'hello ox oxo awesome endo'

Constraints:

• 1 <= sentence.length <= 500

• sentence consists of lowercase and uppercase English letters and spaces.

• Words in sentence are separated by a single space.

• There are no leading or trailing spaces.

Output: Return 'true' if the sentence is circular, otherwise return 'false'.

Example: Output: true

Constraints:

• The sentence will always be non-empty.

Goal: To check if the sentence satisfies the circular condition where the last character of each word matches the first character of the next word.

Steps:

• 1. Split the sentence into words.

• 2. Compare the last character of each word with the first character of the next word.

• 3. Also compare the last character of the last word with the first character of the first word.

Goal: The input sentence follows all given constraints, and the words are composed of only English letters and spaces.

Steps:

• Sentence will always contain valid words with no leading or trailing spaces.

• The words in the sentence will be separated by exactly one space.

Assumptions:

• Words in the sentence are non-empty.

• Words consist only of uppercase and lowercase English letters.

• Input: sentence = 'hello ox oxo awesome endo'

• Explanation: In this example, 'hello' ends with 'o' which matches the first character of 'ox', 'ox' ends with 'x' which matches 'oxo's first character 'x', and so on, forming a circular sentence.

• Input: sentence = 'Leetcode is amazing'

• Explanation: In this case, 'Leetcode' ends with 'e' but 'is' starts with 'i', so the sentence is not circular.

• Input: sentence = 'ax aa a'

• Explanation: Here, 'ax' ends with 'x' but the next word 'aa' starts with 'a', and the pattern does not satisfy the circular condition.

Approach: We check whether each word's last character matches the next word's first character and the first word's first character matches the last word's last character.

Observations:

• We need to check each word and compare the last character with the first character of the next word.

• We also need to ensure the first word and the last word match circularly.

• A simple iteration through the words should allow us to compare adjacent words, with special handling for the first and last word.

Steps:

• 1. Split the sentence into words.

• 2. Check if each word's last character matches the first character of the next word.

• 3. After the loop, compare the last word's last character with the first word's first character.

Empty Inputs:

• The sentence will always be non-empty, so no need to handle empty sentences.

Large Inputs:

• Ensure the solution works efficiently for sentences close to the maximum length of 500 characters.

Special Values:

• The sentence may consist of just one word, in which case we check if the first and last character of the word match.

Constraints:

• Handle sentences of varying lengths, ensuring they adhere to the space and character constraints.

bool isCircularSentence(string s) {
    
    int n = s.size();
    if((s[0]) != (s[n - 1]))
        return false;
    for(int i = 1; i < s.size() - 1; i++) {
        if(s[i] == ' ') {
            if((s[i - 1]) != (s[i + 1]))
                return false;                
        }
    }
    return true;
}

1 : Function Declaration

bool isCircularSentence(string s) {

This line declares the function `isCircularSentence` which takes a string `s` as input and returns a boolean indicating whether the sentence is circular.

2 : Variable Declaration

    int n = s.size();

This line calculates the size of the string `s` and stores it in the variable `n`.

3 : Initial Check

    if((s[0]) != (s[n - 1]))

This conditional checks if the first character of the string `s` is not equal to the last character. If they are not the same, the function returns false.

4 : Early Return

        return false;

If the first and last characters do not match, the sentence is not circular, and the function returns `false`.

5 : Loop Through Sentence

    for(int i = 1; i < s.size() - 1; i++) {

This loop iterates through the string starting from the second character and ends before the last character, checking for spaces and their adjacent characters.

6 : Check for Spaces

        if(s[i] == ' ') {

This line checks if the current character is a space.

7 : Space Validation

            if((s[i - 1]) != (s[i + 1]))

If the current character is a space, this line checks if the character before the space is not equal to the character after the space. If they are not the same, the function returns `false`.

8 : Early Return

                return false;

If the adjacent characters to the space are not equal, the sentence is not circular, and the function returns `false`.

9 : Return True

    return true;

If the entire string passes the checks, the function returns `true`, indicating the sentence is circular.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) where n is the number of characters in the sentence. We process each character once.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the storage of the words in the sentence, but it could be reduced to O(1) if we modify the sentence in place.

Leetcode 2490: Circular Sentence

Explore →