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.
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.
Example 1:
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".
Example 2:
Input: word = "xyxzxe", ch = "z" Output: "zxyxxe" Explanation: The first and only occurrence of "z" is at index 3. Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe".
Example 3:
Input: word = "abcd", ch = "z" Output: "abcd" Explanation: "z" does not exist in word. You should not do any reverse operation, the resulting string is "abcd".
Constraints:
1 <= word.length <= 250word consists of lowercase English letters.ch is a lowercase English letter.The brute force approach involves scanning the string to find the index of the first occurrence of the character and then reversing the substring from the start to that index. If the character is not found, the string remains unchanged. This approach makes use of two operations: the indexOf operation which finds the index of the first occurrence of the character and a reversing operation for the substring.
In this C solution, we first calculate the length of the string. We traverse the string to find the index of the first occurrence of the specified character. If found, we perform a reversal of the substring from start to the found index. The reversed substring is then copied back to a new result string.
C++
Java
Python
C#
JavaScript
The time complexity is O(n) due to the search and reversal operations. The space complexity is O(n) for the storage of the resulting string.
The two-pointers approach is an efficient way to handle the reversed segment directly without using extra space for substring operations. This method entails finding the index of the character first and then reversing the required part of the string in place (where applicable), by gradually swapping elements from both ends of the segment moving inwards.
This C solution utilizes a helper function to reverse a part of the array in place. We locate the index as before, then swap elements utilizing two pointers starting from both ends of the range and working inwards.
C++
Java
Python
C#
JavaScript
The time complexity remains O(n) for the search and in-place reversal. The space complexity is O(1) since no extra space proportional to input size is used.
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n) due to the search and reversal operations. The space complexity is O(n) for the storage of the resulting string. |
| Two Pointers Approach | The time complexity remains O(n) for the search and in-place reversal. The space complexity is O(1) since no extra space proportional to input size is used. |
Reverse Prefix of Word (LeetCode 2000) | Full Solution with stack data structure • Nikhil Lohia • 1,901 views views
Watch 9 more video solutions →Practice Reverse Prefix of Word with our built-in code editor and test cases.
Practice on FleetCode