Backspace Iceren String Karsilastirma

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3291/



Solution 1: Interpreter pattern

	class BackspaceStringCompareInterpreter {
	/**
	* Given two strings S and T, return if they are equal when both are typed into empty text editors.
	*
	* Performance: O(n) time, O(n) space
	*
	* @param S lower case letters with backspace # E.g. ab##
	* @param T lower case chars with backspace # E.g. #a#c
	*
	* @return S contentEquals T
	*/
	public boolean backspaceCompare(String S, String T) {
	Expression expS = constructExpression(S);
	String resultS = expS.interpret();
	Expression expT = constructExpression(T);
	String resultT = expT.interpret();
	return resultS.equals(resultT);
	}
	private Expression constructExpression(String context) {
	Expression exp = null;
	for(char c : context.toCharArray()) {
	if(isLetter(c)) {
	if(exp == null) {
	exp = new CharExpression(c);
	} else {
	exp = new ConcatExpression(exp, new CharExpression(c));
	}
	} else {
	exp = new BackspaceExpression(exp);
	}
	}
	return exp;
	}
	private boolean isLetter(char c) {
	return !isBackspace(c);
	}
	private boolean isBackspace(char c) {
	return c == '#';
	}
	private interface Expression {
	String interpret();
	}
	private class BackspaceExpression implements Expression {
	private Expression before;
	BackspaceExpression(Expression before) {
	this.before = before;
	}
	public String interpret() {
	if(before == null) {
	return "";
	}
	String beforeStr = before.interpret();
	if(beforeStr.length() <= 1) {
	return "";
	}
	return beforeStr.substring(0, beforeStr.length()-1);
	}
	}
	private class ConcatExpression implements Expression {
	private Expression exp1;
	private Expression exp2;
	ConcatExpression(Expression exp1,Expression exp2) {
	this.exp1 = exp1;
	this.exp2 = exp2;
	}
	public String interpret() {
	return new StringBuilder()
	.append(exp1.interpret())
	.append(exp2.interpret())
	.toString();
	}
	}
	private class CharExpression implements Expression {
	private char letter;
	CharExpression(char letter) {
	this.letter = letter;
	}
	public String interpret() {
	return String.valueOf(letter);
	}
	}
	}

view raw BackspaceStringCompareInterpreter.java hosted with ❤ by GitHub

Solution 2: Using Stack

	import java.util.*;
	class BackspaceStringCompareWithStack {
	/**
	* @param S lower case letters with backspace # E.g. ab##
	* @param T lower case chars with backspace # E.g. #a#c
	*
	* @return S contentEquals T
	*/
	public boolean backspaceCompare(String S, String T) {
	String resultS = constructString(S);
	String resultT = constructString(T);
	return resultS.equals(resultT);
	}
	private String constructString(String context) {
	Stack<Character> stack = new Stack<>();
	for(char c : context.toCharArray()) {
	if(isLetter(c)) {
	stack.push(c);
	} else if(!stack.isEmpty()){
	stack.pop();
	}
	}
	return stack.toString();
	}
	private boolean isLetter(char c) {
	return !isBackspace(c);
	}
	private boolean isBackspace(char c) {
	return c == '#';
	}
	}

view raw BackspaceStringCompareWithStack.java hosted with ❤ by GitHub