Leetcode – Truncate Sentence Solution

Spread the love

LeetCode is a platform that offers a collection of coding challenges to help software engineers prepare for interviews. Among these problems is one called “Truncate Sentence,” which is an excellent exercise for those looking to improve their Python skills, particularly in string manipulation and list comprehension. This article provides an in-depth exploration of different methods to solve this problem in Python.

Problem Statement

You are given a sentence as a string s and an integer k. Your task is to truncate the sentence so that it contains only the first k words.

Constraints

  • The sentence consists of at most 10^4 words.
  • The words in the sentence are separated by a single space.
  • There are no leading or trailing spaces.

Examples

  1. Input: s = "Hello how are you", k = 4 Output: "Hello how are you"
  2. Input: s = "What is the solution", k = 4 Output: "What is the solution"
  3. Input: s = "chop chop chop", k = 1 Output: "chop"

Approach 1: The Split and Join Method

The most straightforward approach is to split the sentence into words and then join the first k words to create the truncated sentence.

def truncateSentence(s: str, k: int) -> str:
    words = s.split(" ")
    truncated = " ".join(words[:k])
    return truncated

Time Complexity

The time complexity of this approach is O(n), where n is the length of the input string. This is because the split() function goes through each character to split the string into words.

Space Complexity

The space complexity is also O(n) as we are storing the words in a list.

Approach 2: One-Pass Solution

A more efficient way is to iterate through the sentence and count the words until you reach the kth word.

def truncateSentence(s: str, k: int) -> str:
    count, end = 0, 0
    
    for i, char in enumerate(s):
        if char == ' ':
            count += 1
        if count == k:
            end = i
            break
            
    return s[:end]

Time Complexity

This approach has a time complexity of O(k) because we only iterate through the sentence until the kth word.

Space Complexity

The space complexity is O(1) as we are not using any additional data structures.

Approach 3: Using List Comprehension

This is a more Pythonic solution using list comprehension.

def truncateSentence(s: str, k: int) -> str:
    return ' '.join(s.split(' ')[:k])

This single line of code performs the same operation as the first approach but in a more compact form.

Time and Space Complexity

The time and space complexity are the same as the first approach: O(n).

Unit Testing

It’s crucial to validate your solution with multiple test cases.

def test_truncateSentence():
    assert truncateSentence("Hello how are you", 4) == "Hello how are you"
    assert truncateSentence("What is the solution", 4) == "What is the solution"
    assert truncateSentence("chop chop chop", 1) == "chop"
    print("All test cases pass")

test_truncateSentence()

Conclusion

The “Truncate Sentence” problem is an excellent challenge for those looking to hone their skills in Python string manipulation and list operations. Several approaches, ranging from the straightforward split() and join() methods to a more optimized one-pass solution, can solve this problem efficiently. Understanding the trade-offs between different solutions in terms of time and space complexity is essential for growing as a Python programmer and an algorithmic thinker.

Leave a Reply