Переключение строк по слову за один проход

Question

Есть ли какой-либо алгоритм/метод, в котором изменение строки словами может выполняться за один проход с временной сложностью O (n) и пространственной сложностью O (1).

Answer 1

Если мы можем получить символы в обратном порядке, и каждое слово требует не более O(1) машинных слов в памяти, то для обратного слова в один проход можно использовать O (n) -time, O (1) -пространственный алгоритм (псевдо-код):

def reverse_words(text): 
    word = [] # assume a word requires O(1) machine words 
    for character in reversed(text): # single pass (in reverse) 
     if character == ' ': 
      if word: # print non-empty word 
       print(''.join(reversed(word)), end=character) 
       word = [] 
     else: 
      word.append(character) # O(1)-time 
    if word: # print the first word (in original text) if it is not empty 
     print(''.join(reversed(word))) 

Пример:

>>> reverse_words("this is a string") 
string a is this 

Примечание: каждый символ прикоснулся дважды: первый - добавление, второй - распечатать его. Чтобы понять, почему это еще однопроходный алгоритм, представьте вместо text функцию poplast(), которая выводит (извлекает и удаляет) последний символ из последовательности символов. Если она возвращает None для пустой последовательности, то цикл будет выглядеть так:

for character in iter(poplast, None): # call `poplast()` until it returns `None` 
    # the rest is the same as in the first loop .. 

В этом случае мы не можем сделать больше, чем один проход над входом. Он разрушается на первом проходе.

возможно ли изменить исходный текст?

Да. Снова , если можно считать, что длина длинного слова постоянна (не зависит от n), т. Е. Если n растет; максимальная длина слова остается неизменной.

Просто прочитайте одно слово за раз с обоих концов на два временных буфера. И поменяйте их, сохранив следы неиспользуемых концов из-за неравномерных размеров слов на разных концах. Только один временный буфер не будет пустым после обмена (тот, у которого есть неполное слово). Заполняйте буферы до тех пор, пока не будет найдено полное слово на обоих концах или в центре. Затем повторите своп.

Я не могу придумать элегантную реализацию. И я не вижу смысла однопроходного требования, если у нас есть случайный доступ к вводу. Посмотрите, как реализованы tac utility or tail -r (BSD) (в этом случае строка играет роль одного слова) для очень больших файлов, которые не вписываются в память.

Answer 2

Нет, это невозможно за один проход, если вы уже не знаете, сколько времени у каждого слова или разрешено использовать какой-то буфер.

Попробуйте:

HELLO SAM 
^ 
becomes 
SAM HELLO 
    ^

Если все, что вы знаете, это E (так как это ваш первый/единственный проход, и вы не можете хранить любые данные), вы можете не знать, что, возможно, он должен быть заменен туда, где в данный момент находится символ пробела. Как только вы достигнете места и узнаете, где находится E, слишком поздно снова получить E.

Answer 3

Если рассматривать слово может иметь максимальное количество символов 20, мы можем достичь O (1) пространство, O (N) времени и один проход :)

public static void main(String[] args) { 

     reverse("Hello World HaHa"); 
    } 

    public static void reverse(String line) { 
     char[] stack = new char[20]; 
     int index = 0; 
     for (int i = line.length() - 1; i >= 0; i--) { 
      if (line.charAt(i) != ' ') { 
       stack[index++] = line.charAt(i); 
      } else { 
       while (--index >= 0) { 
        System.out.print(stack[index]); 
       } 
       System.out.print(' '); 
       index = 0; 
      } 
     } 
     if (index > 0) { 
      while (--index >= 0) { 
       System.out.print(stack[index]); 
      } 
     } 
    } 

Примечание: фактическая сложность времени is 2n, где n - длина строки, но один проход!