algorithm - test1

Question

Given a string with “a~z” and “<” that represent you type the keyboard (“<” means backspace).

For example, “abc<<dd<<” represents “a”, and “zzz<<<” represents “”

不會出現刪到空格的情形，例如 “a<<”（我猜實際面試的時候這問題要你自己問）

• 基本 - Implement a function
  bool equal(string, string) that whether the two strings are equal.

• 延伸 1 - Can you avoid using extra O(n) space?

• 延伸 2 - Can you avoid using extra O(n) space and avoid modifying the input string?

Anwser

程式思路:

先做好一個對照組，用 deque 做方便後續驗證，
字串如果從頭掃到尾變數會太大，所以這次的兩個字串應該從尾巴開始往頭掃。兩個字串個別用兩個變數作筆記，

an,bn 為記錄 ‘-‘的數量, ap,bp 為紀錄目前掃到哪個位置。

• int an = 0, bn = 0;
• int ap = a.length() - 1, bp = b.length() - 1;

#include <stdio.h>
#include <deque>
#include <string>
#include <iostream>
using namespace std;

string func(string input) {
    std::deque<char> q;
    for (auto it : input) {
        if (it != '<')
            q.push_back(it);
        else
            if (!q.empty())
                q.pop_back();
    }
    //out << input << " >> "  << string(q.begin(), q.begin()).c_str() << endl;
    return string(q.begin(), q.end());
}
bool equal(string a, string b) {
    return !func(a).compare(func(b));
}
bool equal2(string a, string b) {
    int an = 0, bn = 0;
    int ap = a.length() - 1, bp = b.length() - 1;
    while (ap >= 0 && bp >= 0) {
        //value compare
        if (a[ap] != '<' && b[bp] != '<') {
            if ((an == 0) && (bn == 0)) {
                if (a[ap] != b[bp])
                    return false;
                else
                    ap--, bp--; continue;
            }
        }

        // symbol or letter?
        if (a[ap] == '<')
            an++, ap--;
        else if (an > 0)
            ap--, an--;

        if (b[bp] == '<')
            bn++, bp--;
        else if (bn > 0)
            ap--, bn--;
    }

    //why break?
    if (ap != bp) {
        //final
        while (bp >= 0) {
            if (b[bp] == '<')
                bn++, bp--;
            else //letter
            {
                if (bn > 0)
                    bp--, bn--;
                else
                    break;
            }
        }

        while (ap >= 0) {
            if (a[ap] == '<')
                an++, ap--;
            else //letter
            {
                if (an > 0)
                    ap--, an--;
                else
                    break;
            }
        }
    }
    return (ap == bp) ? true : false;
}

#define YTEST PTEST
#define PRINTF(a,b) printf(#a" "#b" is equal? %s", equal(a, b) ? "yes" : "no");  printf( "  %s\n", equal2(a, b) ? "yes" : "no");
#define PTEST(a,b) printf(#a" "#b"  is pass? %s\n", (equal2(a, b) == equal(a,b)) ? "yes" : "no");

int main() {
    YTEST("aab<c<<dd<", "bazzb<zz<<<<");
    YTEST("aab<<<", "bbb<<<<");
    YTEST("abc", "abc");
    YTEST("abc", "abc<");
    YTEST("abc", "<abc");
    YTEST("abc<<<<<<<<", "<<<<<<<<<");
    YTEST("<<<<<<<<abc<<", "a");
    return 0;
}