Skip to content

2000. Reverse Prefix of Word

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.

 

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 <= 250
  • word consists of lowercase English letters.
  • ch is a lowercase English letter.

Solutions

Solution 1: Simulation

Thinking

The string length satisfies \(n \le 250\), so locating \(ch\) and reversing the prefix is linear. If \(ch\) is absent, the original string is already the answer.

Only the segment through the first occurrence should flip; the suffix stays unchanged. A single find yields index \(i\), or \(-1\) when missing.

Hence slice \(word[i::-1]\) for the reversed prefix and concatenate \(word[i+1:]\).

First, we find the index \(i\) where the character \(ch\) first appears. Then, we reverse the characters from index \(0\) to index \(i\) (including index \(i\)). Finally, we concatenate the reversed string with the string starting from index \(i + 1\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string \(word\).

1
2
3
4
class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        i = word.find(ch)
        return word if i == -1 else word[i::-1] + word[i + 1 :]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public String reversePrefix(String word, char ch) {
        int j = word.indexOf(ch);
        if (j == -1) {
            return word;
        }
        char[] cs = word.toCharArray();
        for (int i = 0; i < j; ++i, --j) {
            char t = cs[i];
            cs[i] = cs[j];
            cs[j] = t;
        }
        return String.valueOf(cs);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    string reversePrefix(string word, char ch) {
        int i = word.find(ch);
        if (i != string::npos) {
            reverse(word.begin(), word.begin() + i + 1);
        }
        return word;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func reversePrefix(word string, ch byte) string {
    j := strings.IndexByte(word, ch)
    if j < 0 {
        return word
    }
    s := []byte(word)
    for i := 0; i < j; i++ {
        s[i], s[j] = s[j], s[i]
        j--
    }
    return string(s)
}

1
2
3
4
5
6
7
function reversePrefix(word: string, ch: string): string {
    const i = word.indexOf(ch) + 1;
    if (!i) {
        return word;
    }
    return [...word.slice(0, i)].reverse().join('') + word.slice(i);
}

1
2
3
4
5
6
7
8
impl Solution {
    pub fn reverse_prefix(word: String, ch: char) -> String {
        match word.find(ch) {
            Some(i) => word[..=i].chars().rev().collect::<String>() + &word[i + 1..],
            None => word,
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    /**
     * @param String $word
     * @param String $ch
     * @return String
     */
    function reversePrefix($word, $ch) {
        $len = strlen($word);
        $rs = '';
        for ($i = 0; $i < $len; $i++) {
            $rs = $rs . $word[$i];
            if ($word[$i] == $ch) {
                break;
            }
        }
        if (strlen($rs) == $len && $rs[$len - 1] != $ch) {
            return $word;
        }
        $rs = strrev($rs);
        $rs = $rs . substr($word, strlen($rs));
        return $rs;
    }
}

Comments