844.backspace-string-compare.cpp

/*
 * @lc app=leetcode id=844 lang=cpp
 *
 * [844] Backspace String Compare
 *
 * https://leetcode.com/problems/backspace-string-compare/description/
 *
 * algorithms
 * Easy (47.14%)
 * Likes:    1009
 * Dislikes: 60
 * Total Accepted:    98K
 * Total Submissions: 207.9K
 * Testcase Example:  '"ab#c"\n"ad#c"'
 *
 * Given two strings S and T, return if they are equal when both are typed into
 * empty text editors. # means a backspace character.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: S = "ab#c", T = "ad#c"
 * Output: true
 * Explanation: Both S and T become "ac".
 * 
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: S = "ab##", T = "c#d#"
 * Output: true
 * Explanation: Both S and T become "".
 * 
 * 
 * 
 * Example 3:
 * 
 * 
 * Input: S = "a##c", T = "#a#c"
 * Output: true
 * Explanation: Both S and T become "c".
 * 
 * 
 * 
 * Example 4:
 * 
 * 
 * Input: S = "a#c", T = "b"
 * Output: false
 * Explanation: S becomes "c" while T becomes "b".
 * 
 * 
 * Note:
 * 
 * 
 * 1 <= S.length <= 200
 * 1 <= T.length <= 200
 * S and T only contain lowercase letters and '#' characters.
 * 
 * 
 * Follow up:
 * 
 * 
 * Can you solve it in O(N) time and O(1) space?
 * 
 * 
 * 
 * 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
	int pos(string& S){
		int i = 0, k = 0;
		while(k<S.size()){
    		if(S[k] == '#')
    			i = max(0, i-1);
    		else
    			S[i++] = S[k];
    		k++;
    	}
    	return i;
	}
    bool backspaceCompare(string S, string T) {
    	int i = pos(S), j = pos(T);
    	if(i != j)	return false;
    	for(i=0; i<j; i++)
    		if(S[i] != T[i])	return false;
    	return true;
    }
};
// @lc code=end