Create 844.Backspace-String-Compare.cpp

wisdompeak · web-flow · commit 19b540eb8080 · 2018-09-26T16:19:11.000-07:00
diff --git a/String/844.Backspace-String-Compare/844.Backspace-String-Compare.cpp b/String/844.Backspace-String-Compare/844.Backspace-String-Compare.cpp
@@ -0,0 +1,36 @@
+class Solution {
+public:
+    bool backspaceCompare(string S, string T) 
+    {        
+        int i = squeeze(S);        
+        int j = squeeze(T);
+        
+        return S.substr(i)==T.substr(j);
+    }
+    
+    int squeeze(string& S)
+    {
+        int i = S.size()-1;
+        int j = S.size()-1;
+        int count = 0;
+        
+        while (i>=0)
+        {
+            while (count>0 || i>=0 && S[i]=='#')
+            {
+                if (S[i]=='#')
+                    count++;
+                else
+                    count--;
+                i--;
+            }
+            if (i>=0)
+            {
+                S[j] = S[i];
+                j--;
+                i--;
+            }            
+        }
+        return j+1;
+    }
+};
