[LeetCode] 844. Backspace String Compare 退格字符串比较

2021年09月15日 阅读数:2
这篇文章主要向大家介绍[LeetCode] 844. Backspace String Compare 退格字符串比较,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.html

Example 1:java

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

Example 2:python

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

Example 3:c#

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

Example 4:app

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:post

  1. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. S and T only contain lowercase letters and '#' characters.

Follow up:url

  • Can you solve it in O(N) time and O(1) space?
给2个字符串S和T,里面含有#表明退格键,意味着前面的字符会被删除,判断2个字符串是否相等,字符串中只含有小写字母和#。
解法1:用一个栈存字符,循环字符串,若是是字母就加入栈,遇到#并且栈里面有字母就pop出栈里最后的字符。T: O(n), S:(n)
解法2:follow up要求O(N) time and O(1) space,在一个循环里,从后往前处理字符串,用一个变量记录要删除的字符数量,遇到#时变量加1,遇到字符而且变量大于1,变量减1,直到没遇到#而且要变量为0,这时比较两个字符此时是否同样,不同返回false,若是字符串比较完没有不同的字符出现,返回ture。
G家:follow up: 若是有大写键CAP
Java: O(1) space
public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        while (true) {
            for (int back = 0; i >= 0 && (back > 0 || S.charAt(i) == '#'); --i)
                back += S.charAt(i) == '#' ? 1 : -1;
            for (int back = 0; j >= 0 && (back > 0 || T.charAt(j) == '#'); --j)
                back += T.charAt(j) == '#' ? 1 : -1;
            if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
                i--; j--;
            } else
                return i == -1 && j == -1;
        }
    }

Python:spa

 def backspaceCompare(self, S, T):
        i, j = len(S) - 1, len(T) - 1
        backS = backT = 0
        while True:
            while i >= 0 and (backS or S[i] == '#'):
                backS += 1 if S[i] == '#' else -1
                i -= 1
            while j >= 0 and (backT or T[j] == '#'):
                backT += 1 if T[j] == '#' else -1
                j -= 1
            if not (i >= 0 and j >= 0 and S[i] == T[j]):
                return i == j == -1
            i, j = i - 1, j - 1

Python:code

# Time:  O(m + n)
# Space: O(1)
import itertools

class Solution(object):
    def backspaceCompare(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        def findNextChar(S):
            skip = 0
            for i in reversed(xrange(len(S))):
                if S[i] == '#':
                    skip += 1
                elif skip:
                    skip -= 1
                else:
                    yield S[i]

        return all(x == y for x, y in
                   itertools.izip_longest(findNextChar(S), findNextChar(T)))

Python: wo O(n) spacehtm

class Solution(object):
    def backspaceCompare(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        s1, s2 = [], []
        for i in range(len(S)):
            if S[i] == '#' and s1:
                s1.pop()
            elif S[i] == '#':
                continue
            else:
                s1.append(S[i])
        
        for j in range(len(T)):
            if T[j] == '#' and s2:
                s2.pop()
            elif T[j] == '#':
                continue
            else:
                s2.append(T[j])
        
        return s1 == s2

C++:  

bool backspaceCompare(string S, string T) {
        int i = S.length() - 1, j = T.length() - 1;
        while (1) {
            for (int back = 0; i >= 0 && (back || S[i] == '#'); --i)
                back += S[i] == '#' ? 1 : -1;
            for (int back = 0; j >= 0 && (back || T[j] == '#'); --j)
                back += T[j] == '#' ? 1 : -1;
            if (i >= 0 && j >= 0 && S[i] == T[j])
                i--, j--;
            else
                return i == -1 && j == -1;
        }
    }

  

  

 

All LeetCode Questions List 题目汇总