iframe-proxy | Sunbelt Computer Software

History

79 lines (70 loc) · 1.86 KB

Raw

// Author: Shobhit Behl (LC: shobhitbruh)

class Solution {

public boolean backspaceCompare(String s, String t) {

Stack<Character> st1=new Stack<>();

Stack<Character> st2=new Stack<>();

for(int i=0;i<s.length();i++){

if(s.charAt(i)=='#'){

if(st1.size()>0){

st1.pop();

}

}else{

st1.push(s.charAt(i));

}

for(int i=0;i<t.length();i++){

if(t.charAt(i)=='#'){

if(st2.size()>0){

st2.pop();

}

}else{

st2.push(t.charAt(i));

}

return st1.equals(st2);

}

// @saorav21994

// TC : O(n)

// SC : O(1)

// Follow up solution with O(1) space

class Solution {

public boolean backspaceCompare(String s, String t) {

int sl = s.length();

int tl = t.length();

StringBuffer sb = new StringBuffer("");

int back = 0;

for (int i = sl-1; i >= 0; i--) {

if (s.charAt(i) == '#')

back += 1;

else {

if (back > 0) {

back -= 1;

continue;

}

sb.insert(0, s.charAt(i));

}

back = 0;

int j = sb.length();

for (int i = tl-1; i >= 0; i--) {

if (t.charAt(i) == '#') {

back += 1;

}

else {

if (back > 0) {

back -= 1;

continue;

}

j -= 1;

if (j >= 0) {

if (t.charAt(i) != sb.charAt(j))

return false;

}

if (j != 0)

return false;

return true;

}

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

BackspaceStringCompare.java

Latest commit

History

BackspaceStringCompare.java

File metadata and controls