Given two strings S and T, return if they’re equal when each are typed into empty textual content editors. # means a backspace character.

Instance 1:
Enter: S = “ab#c”, T = “advert#c”
Output: true
Rationalization: Each S and T turn out to be “ac”.

Instance 2:
Enter: S = “ab##”, T = “c#d#”
Output: true
Rationalization: Each S and T turn out to be “”.

Instance 3:
Enter: S = “a##c”, T = “#a#c”
Output: true
Rationalization: Each S and T turn out to be “c”.

Instance 4:
Enter: S = “a#c”, T = “b”
Output: false
Rationalization: S turns into “c” whereas T turns into “b”.

Be aware:
1 <= S.size <= 200
1 <= T.size <= 200
S and T solely comprise lowercase letters and ‘#’ characters. Are you able to clear up it in O(N) time and O(1) house?

Javascript algorithm to carry out backspace string comparability

To simulate the backspace key, we are able to use a stack, and carry out a pop operation after we need to delete earlier character. In Javascript, we are able to use Array.prototype.pop() to take away the final aspect (which could be referred to as on empty array and that returns undefined). Once we iterate all characters, we have to be part of the stack/array as a string. Then, the final step is to carry out a string comparisons.

1 2 Three Four 5 6 7 eight 9 10 11 12 13 14 15 16 17 18 19 
/**  * @param {string} S  * @param {string} T  * @return {boolean}  */ var backspaceCompare = operate(S, T) {     const construct = (S) => {         let st = [];                 for (let i = 0, len = S.size; i < len; ++ i) {             if (S[i] == '#') {                 st.pop(); // if referred to as on empty array, return undefined.             } else {                 st.push(S[i]);             }         }         return st.be part of('');     }     return construct(S) === construct(T); };
/**  * @param {string} S  * @param {string} T  * @return {boolean}  */ var backspaceCompare = operate(S, T) {     const construct = (S) => {         let st = [];                 for (let i = 0, len = S.size; i < len; ++ i) {             if (S[i] == '#') {                 st.pop(); // if referred to as on empty array, return undefined.             } else {                 st.push(S[i]);             }         }         return st.be part of('');     }     return construct(S) === construct(T); };

String backspace comparability in C++

Barely otherwise, we don’t assemble/be part of the characters within the stack, as an alternative, we are able to carry out comparisons on each stacks generated from two enter strings.

1 2 Three Four 5 6 7 eight 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
class Answer { public:     bool backspaceCompare(string S, string T) {         stack<char> st1 = realString(S);         stack<char> st2 = realString(T);         if (st1.dimension() != st2.dimension()) return false;         whereas (st1.dimension() > 0) {             char p1 = st1.prime();             char p2 = st2.prime();             st1.pop();             st2.pop();             if (p1 != p2) return false;         }         return true;     }      personal:     stack<char> realString(string S) {         stack<char> st;             for (int i = 0; i < S.dimension(); ++ i) {             if (S[i] == '#') {                 if (st.dimension() > 0) {                     st.pop();                 }             } else {                 st.push(S[i]);             }         }         return st;     } };
class Answer { public:     bool backspaceCompare(string S, string T) {         stack<char> st1 = realString(S);         stack<char> st2 = realString(T);         if (st1.dimension() != st2.dimension()) return false;         whereas (st1.dimension() > 0) {             char p1 = st1.prime();             char p2 = st2.prime();             st1.pop();             st2.pop();             if (p1 != p2) return false;         }         return true;     }      personal:     stack<char> realString(string S) {         stack<char> st;             for (int i = 0; i < S.dimension(); ++ i) {             if (S[i] == '#') {                 if (st.dimension() > 0) {                     st.pop();                 }             } else {                 st.push(S[i]);             }         }         return st;     } };

Java implementation of string backspace comparisons

We are able to use String.valueOf(stack) to transform the stack of characters into String.

1 2 Three Four 5 6 7 eight 9 10 11 12 13 14 15 16 
class Answer {     public boolean backspaceCompare(String S, String T) {         return construct(S).equals(construct(T));     }       public String construct(String S) {         Stack<Character> ans = new Stack();         for (char c: S.toCharArray()) {             if (c != '#')                 ans.push(c);             else if (!ans.empty())                 ans.pop();         }         return String.valueOf(ans);     } }
class Answer {     public boolean backspaceCompare(String S, String T) {         return construct(S).equals(construct(T));     }      public String construct(String S) {         Stack<Character> ans = new Stack();         for (char c: S.toCharArray()) {             if (c != '#')                 ans.push(c);             else if (!ans.empty())                 ans.pop();         }         return String.valueOf(ans);     } }

All above implementations run at complexity O(M + N) in each time and house the place M and N are the lengths of enter strings S and T respectively.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Ranking
loading…

573 phrases
– Assist my work by way of Donations (Thanks):Final Put up: The Alien Dictionary Verification Algorithm