Solution Explanation for Reverse Prefix of Word

This problem requires reversing a prefix of a given string up to the first occurrence of a specific character. The solution involves several steps:

1. Find the character: We first locate the index of the first occurrence of the character ch within the input string word. Built-in string functions like find() (Python), indexOf() (Java, Javascript), or IndexByte() (Go) efficiently handle this. If ch is not found, the index will be -1 or a similar negative value indicating no occurrence.

2. Reverse the prefix: If ch is found (index is not negative), we reverse the portion of the string from index 0 up to and including the index of ch. Several approaches exist for this:

   • In-place reversal: This is generally the most efficient, involving swapping characters from the beginning and end of the prefix, moving inwards until the middle is reached. This is demonstrated in the Java and Go solutions.

   • Slicing and reversing: Languages like Python allow easy string slicing and built-in reverse functions. The Python solution demonstrates this concise approach. The TypeScript solution also uses this method.

   • Using reverse() function: C++ provides a reverse() function that directly operates on a portion of a string.

3. Concatenate: Finally, we concatenate the reversed prefix with the remaining portion of the original string (from the index of ch + 1 to the end) to form the final result.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the input string word. This is because we iterate through the string at most once to find the character and potentially once more to reverse the prefix (in-place reversal is still O(n) in the worst case).

• Space Complexity: O(n) in the worst case. While in-place reversal uses constant extra space, the creation of a new string (explicit concatenation or through implicit string manipulation in some languages) can require O(n) additional space to hold the result. However, some solutions may optimize this in cases where in-place modification is possible (like the Java and Go solutions). The Python solution utilizes string slicing, which might involve creating temporary strings internally.

Code Examples (Detailed)

The provided solutions showcase different approaches across various languages. Key aspects are highlighted below:

Python:

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        i = word.find(ch)  #Efficiently finds the index of 'ch'
        return word if i == -1 else word[i::-1] + word[i + 1:] #Slicing and reversing

This leverages Python's powerful string slicing capabilities for a compact and readable solution. word[i::-1] reverses the prefix.

Java:

class Solution {
    public String reversePrefix(String word, char ch) {
        int j = word.indexOf(ch); //Finds the index
        if (j == -1) {
            return word;
        }
        char[] cs = word.toCharArray(); // Converts to char array for in-place reversal
        for (int i = 0; i < j; ++i, --j) { //In-place reversal
            char t = cs[i];
            cs[i] = cs[j];
            cs[j] = t;
        }
        return String.valueOf(cs); //Converts back to String
    }
}

This shows in-place reversal for optimal space efficiency.

C++:

class Solution {
public:
    string reversePrefix(string word, char ch) {
        int i = word.find(ch);  //Finds index
        if (i != string::npos) { //string::npos indicates 'ch' not found
            reverse(word.begin(), word.begin() + i + 1); //uses the std::reverse function
        }
        return word;
    }
};

This directly uses the std::reverse algorithm for efficient reversal.

The other language examples follow similar principles, adapting to the specific syntax and features of each language. The choice of method (in-place reversal vs. slicing/reversing) influences the space complexity slightly, but the overall time complexity remains O(n) in all cases.