Leetcode 2000 - Reverse Prefix of Word

Problem Description

Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.

For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd". Return the resulting string.

Examples

Input: word = "abcdefd", ch = "d"

Output: "dcbaefd"

Explanation: The first occurrence of "d" is at index 3. Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd".Input: word =

Thought Process / Intuition

Straightforward question, reverse the string up to the first occurence of the letter. Otherwise, do nothing. To accomplish this, I thought of using a queue and appendleft until i met the first occurence, then append normally in order to simulate the reversal. However, that only works if we are guaranteed an occurence of the char. In the event of no occurence, we can simply return the original string. As such, I realised we can just add to a stack, which is a python List, and just reverse the list when we encounter the first occurence of the char, then continue adding to the stack. Finally, we can join the stack and return the string.

Approach

1. We initialize an empty list res to store the reversed string.
2. We iterate through the string word and append each character to the list res.
3. If we encounter the character ch, we reverse the list res and break out of the loop.
4. We continue iterating through the string word and append each character to the list res.
5. We join the list res to form the resulting string and return it.

Solution

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        res = []
        index = 0
        for i in range(len(word)):
            index += 1
            res.append(word[i])
            if word[i] == ch:
                res.reverse()
                break
        for j in range(index, len(word)):
            res.append(word[j])
        return ''.join(res)

Complexity Analysis

Time complexity: $O(n)$

• The time complexity of the solution is $O(n)$, where $n$ is the length of the input string word. We iterate through the string word once to reverse the prefix segment.
• The time complexity of the reverse() function is $O(n)$, where $n$ is the length of the list res.
• The overall time complexity is $O(n)$.

Space complexity: $O(n)$

• The space complexity of the solution is $O(n)$.
• We use a list res to store the characters of the input string word.
• The space complexity of the list res is $O(n)$, where $n$ is the length of the input string word.

Shoutout to My Friends' Solutions on Leetcode

My Solution

Si Yuan's Solution