План курса / Все задачи / Алгоритмы и структуры данных

Сравнение строк вида a#bc#

сложно

# решено

Даны строки s и t. Нужно вернуть true в случае, если строки будут одинаковыми после ввода в текстовый редактор. Символ # в текстовом редакторе означает, что предыдущий символ нужно стереть, а если перед # отсутствует символ, то стирать ничего не нужно.

Пример 1:

Ввод: s = "ac#b#ac", t = "abc##aa#b#c"
Вывод: true
Объяснение: "aac" = "aac"

Пример 2:

Ввод: s = "a#####b", t = "b"
Вывод: true
Объяснение: "b" = "b"

Пример 3:

Ввод: s = "abcd", t = "abcd#"
Вывод: false

Ограничения:

len(s), len(t) >= 0

function findNextNonSkip(s, i) {
    let skipCount = 0;
    while (i >= 0 && (skipCount > 0 || s[i] === '#')) {
        if (s[i] === '#') {
            skipCount += 1;
            i -= 1;
            continue;
        }
        skipCount -= 1;
        i -= 1;
    }
    return i;
}

export function compare(s, t) {
    let p1 = s.length;
    let p2 = t.length;

    while (p1 > 0 && p2 > 0) {
        p1 = findNextNonSkip(s, p1 - 1);
        p2 = findNextNonSkip(t, p2 - 1);
        
        if (p1 >= 0 && p2 >= 0 && s[p1] !== t[p2]) {
            return false;
        }
    }

    return findNextNonSkip(s, p1 - 1) === findNextNonSkip(t, p2 - 1);
}

public class Solution
{
    static int FindNextNonSkip(string s, int i)
    {
        int skipCount = 0;
        while (i >= 0 && (skipCount > 0 || s[i] == '#'))
        {
            if (s[i] == '#')
            {
                skipCount++;
                i--;
                continue;
            }
            skipCount--;
            i--;
        }
        return i;
    }

    public static bool Compare(string s, string t)
    {
        int p1 = s.Length;
        int p2 = t.Length;

        while (p1 > 0 && p2 > 0)
        {
            p1 = FindNextNonSkip(s, p1 - 1);
            p2 = FindNextNonSkip(t, p2 - 1);

            if (p1 >= 0 && p2 >= 0 && s[p1] != t[p2])
            {
                return false;
            }
        }
        return FindNextNonSkip(s, p1 - 1) == FindNextNonSkip(t, p2 - 1);
    }
}

#include <string>

using namespace std;

int findNextNonSkip(const string& s, int i) {
    int skipCount = 0;
    while (i >= 0 && (skipCount > 0 || s[i] == '#')) {
        if (s[i] == '#') {
            skipCount++;
            i--;
            continue;
        }
        skipCount--;
        i--;
    }
    return i;
}

bool compare(const string& s, const string& t) {
    int p1 = s.size();
    int p2 = t.size();
    
    while (p1 > 0 && p2 > 0) {
        p1 = findNextNonSkip(s, p1 - 1);
        p2 = findNextNonSkip(t, p2 - 1);
        if (p1 >= 0 && p2 >= 0 && s[p1] != t[p2]) {
            return false;
        }
    }
    return findNextNonSkip(s, p1 - 1) == findNextNonSkip(t, p2 - 1);
}

package main

func findNextNonSkip(s string, i int) int {
    skipCount := 0
    for i >= 0 && (skipCount > 0 || s[i] == '#') {
        if s[i] == '#' {
            skipCount++
            i--
            continue
        }
        skipCount--
        i--
    }
    return i
}

func compare(s string, t string) bool {
    p1 := len(s)
    p2 := len(t)
    
    for p1 > 0 && p2 > 0 {
        p1 = findNextNonSkip(s, p1-1)
        p2 = findNextNonSkip(t, p2-1)
        if p1 >= 0 && p2 >= 0 && s[p1] != t[p2] {
            return false
        }
    }
    return findNextNonSkip(s, p1-1) == findNextNonSkip(t, p2-1)
}

public class Solution {
    private int findNextNonSkip(String s, int i) {
        int skipCount = 0;
        while (i >= 0 && (skipCount > 0 || s.charAt(i) == '#')) {
            if (s.charAt(i) == '#') {
                skipCount++;
                i--;
                continue;
            }
            skipCount--;
            i--;
        }
        return i;
    }

    public boolean compare(String s, String t) {
        int p1 = s.length();
        int p2 = t.length();
        
        while (p1 > 0 && p2 > 0) {
            p1 = findNextNonSkip(s, p1 - 1);
            p2 = findNextNonSkip(t, p2 - 1);
            if (p1 >= 0 && p2 >= 0 && s.charAt(p1) != t.charAt(p2)) {
                return false;
            }
        }
        return findNextNonSkip(s, p1 - 1) == findNextNonSkip(t, p2 - 1);
    }
}

from typing import *

def findNextNonSkip(s: str, i: int) -> int:
    skipCount = 0
    while i >= 0 and (skipCount > 0 or s[i] == '#'):
        if s[i] == '#':
            skipCount += 1
            i -= 1
            continue
        skipCount -= 1
        i -= 1
    return i

def compare(s: str, t: str) -> bool:
    p1, p2 = len(s), len(t)
    while p1 > 0 and p2 > 0:
        p1 = findNextNonSkip(s, p1 - 1)
        p2 = findNextNonSkip(t, p2 - 1)
        if p1 >= 0 and p2 >= 0 and s[p1] != t[p2]:
            return False
    return findNextNonSkip(s, p1 - 1) == findNextNonSkip(t, p2 - 1)

Оценка сложности

Время: O(n+m), где n - размер строки s, m - размер строки t
Память: O(1)

Альтернативное решение

public class Solution {
    public static bool Compare(string s, string t) {
        int p1 = s.Length - 1;
        int p2 = t.Length - 1;
        int p1HashtagCounter = 0;
        int p2HashtagCounter = 0;

        while (p1 >= 0 || p2 >= 0) {
            if (p1 >= 0 && s[p1] == '#') {
                p1HashtagCounter++;
                p1--;
                continue;
            }

            if (p2 >= 0 && t[p2] == '#') {
                p2HashtagCounter++;
                p2--;
                continue;
            }

            if (p1 >= 0 && p1HashtagCounter > 0) {
                p1--;
                p1HashtagCounter--;
                continue;
            }

            if (p2 >= 0 && p2HashtagCounter > 0) {
                p2--;
                p2HashtagCounter--;
                continue;
            }

            if (p1 >= 0 && p2 >= 0 && s[p1] == t[p2]) {
                p1--;
                p2--;
            } else {
                return false;
            }
        }
        return true;
    }
}

#include <string>

using namespace std;

bool compare(const string& s, const string& t) {
    int p1 = static_cast<int>(s.size()) - 1;
    int p2 = static_cast<int>(t.size()) - 1;
    int p1HashtagCounter = 0;
    int p2HashtagCounter = 0;

    while (p1 >= 0 || p2 >= 0) {
        if (p1 >= 0 && s[p1] == '#') {
            ++p1HashtagCounter;
            --p1;
            continue;
        }

        if (p2 >= 0 && t[p2] == '#') {
            ++p2HashtagCounter;
            --p2;
            continue;
        }

        if (p1 >= 0 && p1HashtagCounter > 0) {
            --p1;
            --p1HashtagCounter;
            continue;
        }

        if (p2 >= 0 && p2HashtagCounter > 0) {
            --p2;
            --p2HashtagCounter;
            continue;
        }

        if (p1 >= 0 && p2 >= 0 && s[p1] == t[p2]) {
            --p1;
            --p2;
        } else {
            return false;
        }
    }
    return true;
}

package main

func compare(s string, t string) bool {
    p1 := len(s) - 1
    p2 := len(t) - 1
    p1HashtagCounter := 0
    p2HashtagCounter := 0

    for p1 >= 0 || p2 >= 0 {
        if p1 >= 0 && s[p1] == '#' {
            p1HashtagCounter++
            p1--
            continue
        }

        if p2 >= 0 && t[p2] == '#' {
            p2HashtagCounter++
            p2--
            continue
        }

        if p1 >= 0 && p1HashtagCounter > 0 {
            p1--
            p1HashtagCounter--
            continue
        }

        if p2 >= 0 && p2HashtagCounter > 0 {
            p2--
            p2HashtagCounter--
            continue
        }

        if p1 >= 0 && p2 >= 0 && s[p1] == t[p2] {
            p1--
            p2--
        } else {
            return false
        }
    }
    return true
}

public class Solution {
    public boolean compare(String s, String t) {
        int p1 = s.length() - 1;
        int p2 = t.length() - 1;
        int p1HashtagCounter = 0;
        int p2HashtagCounter = 0;

        while (p1 >= 0 || p2 >= 0) {
            if (p1 >= 0 && s.charAt(p1) == '#') {
                p1HashtagCounter += 1;
                p1 -= 1;
                continue;
            }

            if (p2 >= 0 && t.charAt(p2) == '#') {
                p2HashtagCounter += 1;
                p2 -= 1;
                continue;
            }

            if (p1 >= 0 && p1HashtagCounter > 0) {
                p1 -= 1;
                p1HashtagCounter -= 1;
                continue;
            }

            if (p2 >= 0 && p2HashtagCounter > 0) {
                p2 -= 1;
                p2HashtagCounter -= 1;
                continue;
            }

            if (p1 >= 0 && p2 >= 0 && s.charAt(p1) == t.charAt(p2)) {
                p1 -= 1;
                p2 -= 1;
            } else {
                // один закончился, другой нет
                return false;
            }
        }
        return true;
    }
}

from typing import *

def compare(s: str, t: str) -> bool:
    p1 = len(s) - 1
    p2 = len(t) - 1
    p1_hashtag_counter = 0
    p2_hashtag_counter = 0

    while p1 >= 0 or p2 >= 0:
        if p1 >= 0 and s[p1] == '#':
            p1_hashtag_counter += 1
            p1 -= 1
            continue

        if p2 >= 0 and t[p2] == '#':
            p2_hashtag_counter += 1
            p2 -= 1
            continue

        if p1 >= 0 and p1_hashtag_counter > 0:
            p1 -= 1
            p1_hashtag_counter -= 1
            continue

        if p2 >= 0 and p2_hashtag_counter > 0:
            p2 -= 1
            p2_hashtag_counter -= 1
            continue

        if p1 >= 0 and p2 >= 0 and s[p1] == t[p2]:
            p1 -= 1
            p2 -= 1
        else:
            return False
    return True

from typing import *

def compare(s: str, t: str) -> bool:
    p1 = len(s) - 1
    p2 = len(t) - 1
    p1_hashtag_counter = 0
    p2_hashtag_counter = 0

    while p1 >= 0 or p2 >= 0:
        if p1 >= 0 and s[p1] == '#':
            p1_hashtag_counter += 1
            p1 -= 1
            continue

        if p2 >= 0 and t[p2] == '#':
            p2_hashtag_counter += 1
            p2 -= 1
            continue

        if p1 >= 0 and p1_hashtag_counter > 0:
            p1 -= 1
            p1_hashtag_counter -= 1
            continue

        if p2 >= 0 and p2_hashtag_counter > 0:
            p2 -= 1
            p2_hashtag_counter -= 1
            continue

        if p1 >= 0 and p2 >= 0 and s[p1] == t[p2]:
            p1 -= 1
            p2 -= 1
        else:
            return False
    return True

Оценка сложности

Время: O(n+m), где n - размер строки s, m - размер строки t
Память: O(1)

Это решение не уступает предыдущему по качеству и просто предлагает другой способ реализации. Бери то, которое наиболее понятно!