FRTKL

844. Backspace String Compare (Easy)

Problem

https://leetcode.com/problems/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.
  • Note that after backspacing an empty text, the text will continue empty.

Example 1:

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

Solution

Go

func trim(s string) string {
    b := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++  {
        if s[i] == '#' {
            if len(b) != 0 {
                b = b[:len(b)-1]
            }
        } else {
            b = append(b, s[i])
        }
    }
    return string(b)
}

func backspaceCompare(S string, T string) bool {
    return trim(S) == trim(T)
}

PHP

class Solution {

    /**
     * @param String $S
     * @param String $T
     * @return Boolean
     */
    function backspaceCompare($S, $T) {     
        while (strpos($S, '#') !== false) {
            $S = ltrim($S, '#');
            $S = preg_replace('/[a-z]{1}#/', '', $S);
        }

        while (strpos($T, '#') !== false) {
            $T = ltrim($T, '#');
            $T = preg_replace('/[a-z]{1}#/', '', $T);
        }
        
        return $S === $T;
    }
}

Impression

  • PHPの解き方は他にはあまりなさそうな答え方
    • 「?#」という文字列を再帰的にリプレイスし続ける感じ
    • 頭に「#」がくるパターンが邪魔だったのでltrim() で除外するようにした
  • Goの解き方は1文字ずつ分解して解く感じ
    • 簡易スライス式 で新しいスライスを作成するのがポイント
Written By Fukuaki TAKANO
fortkle icon

Engineering Manager at Connehito inc.
Please contact me via twitter. @fortkle