• Leetcode POTDs

Problem 2490 Circular Sentence

Problem Statement

Link - Problem 2490

Question

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.

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.

Solution

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

Complexity Analysis

| Algorithm        | Time Complexity | Space Complexity |
| ---------------- | --------------- | ---------------- |
| String traversal | O(N)            | O(1)             |

Explanation

1. Intuition

• This question is relatively straightforward.
• A circular sentence is a sentence where the last character of a word is equal to the first character of the next word.
• Also since a sentence cant have leading or trailing spaces, we also need to check if the last character of the last word is equal to the first character of the first word.
• Idea is to traverse the string and whenever encounter a space, check the last character of the previous word and the first character of the next word.
• Whenever we find a mismatch, return false.
• If we reach the end of the string, check if the last character of the last word is equal to the first character of the first word.
• If it is, return true, else return false.

2. Implementation

- For every character `s[i]` in the string do the following:
  - If `s[i]` is a space,
    check if `s[i-1]` is equal to `s[i+1]`.
  - If it is not, return `false`.
- If we reach the end of the string, check if `s[s.size()-1]` is equal to `s[0]`.
- If it is, return `true`, else return `false`.

Easy problem, but a good one to practice string manipulation.