algoadvance

Leetcode 2490. Circular Sentence

Problem Statement

Given a sentence that consists of only lowercase English letters and spaces, we say that the sentence is circular if the last character of a word is the same as the first character of the next word. Your task is to determine whether a given sentence is circular.

For example, the sentence "leetcode exercises sound delightful" is circular because the last character of each word matches the first character of the next word:

Write a function to determine if the given sentence is circular.

Clarifying Questions

  1. Input Constraints:
    • Can the input string be empty? (Assume no—always at least one word)
    • Can there be multiple spaces between words? (Assume no—exactly one space between words)
    • Can the input string contain punctuation? (Assume no—only lowercase English letters and spaces)
  2. Output:
    • Should the function return a boolean value indicating if the sentence is circular? (Yes)

Strategy

To solve this problem, we can follow these steps:

  1. Split the sentence into individual words.
  2. Iterate through the list of words and check if the last character of the current word matches the first character of the next word.
  3. As it’s a circular sentence, don’t forget to check if the last character of the last word matches the first character of the first word.

Code

Here is the C++ code to implement this logic:

#include <iostream>
#include <vector>
#include <sstream>

bool isCircularSentence(const std::string& sentence) {
    std::vector<std::string> words;
    std::stringstream ss(sentence);
    std::string word;
    
    // Split the sentence into words
    while (ss >> word) {
        words.push_back(word);
    }
    
    int n = words.size();
    for (int i = 0; i < n; ++i) {
        char lastChar = words[i].back();
        char firstCharNext = words[(i + 1) % n].front();
        if (lastChar != firstCharNext) {
            return false;
        }
    }
    
    return true;
}

int main() {
    std::string sentence = "leetcode exercises sound delightful";
    if (isCircularSentence(sentence)) {
        std::cout << "The sentence is circular." << std::endl;
    } else {
        std::cout << "The sentence is not circular." << std::endl;
    }
    return 0;
}

Time Complexity

Thus, the overall time complexity of the solution is O(n + m). Since m (number of words) is typically much smaller than n (number of characters in the sentence), the dominant term is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI