Развернуть строку(массив) за O(n) (Two-pointer technique)

Есть типичная задача на собеседовании — развернуть строку. Либо массив, что, в принципе, одно и то же.

Вариантов решения много, самый простой и быстрый — использовать класс StringBuilder:

public void reverseString(char[] s) {
     StringBuilder sb = new StringBuilder(new String(s));
     sb.reverse();     
}

Но если запрещено использовать сторонние классы, то оптимальный вариант — использование two-pointer technique. Суть в том, что определив сразу 2 указателя можно заменить все элементы в один проход, надо только ввести новую буферную переменную:

public void reverseString(char[] s) {
    int i = 0;
    int j = s.length - 1;
    char temp;
    while (i < j) {
        temp = s[i];
        s[i] = s[j];
        s[j] = temp;
        i++;
        j--;
    }            
}
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Leave A Comment

Please be polite. We appreciate that. Your email address will not be published and required fields are marked