Эффективный в пространстве алгоритм проверки, равны ли строки с пробелами? - PullRequest
Новая
       40

Эффективный в пространстве алгоритм проверки, равны ли строки с пробелами?

14 голосов
/ 16 июня 2019

Мне недавно задали этот вопрос в интервью:

Если заданы две строки s и t, вернуть, если они равны, когда обе они введены в пустые текстовые редакторы.# означает символ возврата на одну позицию. 

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Я придумала следующее решение, но оно неэффективно: 

  public static boolean sol(String s, String t) {
    return helper(s).equals(helper(t));
  }

  public static String helper(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
      if (c != '#')
        stack.push(c);
      else if (!stack.empty())
        stack.pop();
    }
    return String.valueOf(stack);
  }

Я хотел посмотреть, есть ли лучший способчтобы решить эту проблему, которая не использует стек.Я имею в виду, можем ли мы решить это в O (1) пространстве сложности?

Примечание: у нас также может быть несколько символов возврата.

Ответы [ 2 ]

12 голосов
/ 16 июня 2019

Чтобы достичь O(1) сложности пространства, используйте Два указателя и начинайте с конца строки: 

public static boolean sol(String s, String t) {
    int i = s.length() - 1;
    int j = t.length() - 1;
    while (i >= 0 || j >= 0) {
        i = consume(s, i);
        j = consume(t, j);
        if (i >= 0 && j >= 0 && s.charAt(i) == t.charAt(j)) {
            i--;
            j--;
        } else {
            return i == -1 && j == -1;
        }
    }
    return true;
}

Основная идея заключается в поддержании #счетчик: увеличение cnt, если символ #, иначе уменьшить его.А если cnt > 0 и s.charAt(pos) != '#' - пропустить символ (позиция уменьшения): 

private static int consume(String s, int pos) {
    int cnt = 0;
    while (pos >= 0 && (s.charAt(pos) == '#' || cnt > 0)) {
        cnt += (s.charAt(pos) == '#') ? +1 : -1;
        pos--;
    }
    return pos;
}

Сложность времени: O(n).

Источник 1 , Источник 2 .

2 голосов
/ 16 июня 2019

Исправленный псевдокод templatetypedef 

// Index of next spot to read from each string
let sIndex = s.length() - 1
let tIndex = t.length() - 1
let sSkip = 0
let tSkip = 0

while sIndex >= 0 and tIndex >= 0:
    if s[sIndex] = #:
        sIndex = sIndex - 1
        sSkip = sSkip + 1
        continue
    else if sSkip > 0
        sIndex = sIndex - 1
        sSkip = sSkip - 1
        continue

    // Do the same thing for t.
    if t[tIndex] = #:
        tIndex = tIndex - 1
        tSkip = tSkip + 1
        continue
    else if tSkip > 0
        tIndex = tIndex - 1
        tSkip = tSkip - 1
        continue

    // Compare characters.
    if s[sIndex] != t[tIndex], return false

    // Back up to the next character
    sIndex = sIndex - 1
    tIndex = tIndex - 1

// The strings match if we’ve exhausted all characters.
return sIndex < 0 and tIndex < 0
...