FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
coding-Interview/BackspaceStringCompare.java at master · arjunmullick/coding-Interview · GitHub
arjunmullick
/
coding-Interview
Public
Notifications
You must be signed in to change notification settings
Fork
1
Star
3
Code
Issues
0
Pull requests
0
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
coding-Interview
/
BackspaceStringCompare.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
90 lines (74 loc) · 2.16 KB
Breadcrumbs
coding-Interview
/
BackspaceStringCompare.java
Copy path
File metadata and controls
90 lines (74 loc) · 2.16 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package
com
.
leetcode
;
import
java
.
util
.
LinkedList
;
import
java
.
util
.
List
;
public
class
BackspaceStringCompare
{
//https://leetcode.com/problems/backspace-string-compare/
class
Solution
{
/**
* "ab##"
* "c#d#"
* <p>
* or
* <p>
* "bxj##tw"
* "bxo#j##tw"
* Special case
**/
//Follow up: O(1) Space
public
boolean
backspaceCompare
(
String
S
,
String
T
) {
int
ns
=
S
.
length
();
int
nt
=
T
.
length
();
int
i
=
ns
-
1
;
int
j
=
nt
-
1
;
while
(
true
) {
//cannot check i>=0 and j>=0 as both shoud finish
int
back
=
0
;
while
(
i
>=
0
&& (
back
>
0
||
S
.
charAt
(
i
) ==
'#'
)) {
if
(
S
.
charAt
(
i
) ==
'#'
) {
back
++;
}
else
{
back
--;
}
i
--;
}
back
=
0
;
while
(
j
>=
0
&& (
back
>
0
||
T
.
charAt
(
j
) ==
'#'
)) {
if
(
T
.
charAt
(
j
) ==
'#'
) {
back
++;
}
else
{
back
--;
}
j
--;
}
if
(
i
>=
0
&&
j
>=
0
&&
S
.
charAt
(
i
) ==
T
.
charAt
(
j
)) {
i
--;
j
--;
}
else
{
break
;
}
}
//System.out.print(i + "" + j);
return
i
== -
1
&&
j
== -
1
;
//covered all index
}
}
}
/**
//With Memory and use of List
String sT = trasnform(S);
String tT = trasnform(T);
System.out.print(sT+" " + tT);
return sT.equals(tT);
public String trasnform(String s){
int n = s.length();
List<Character> ch = new LinkedList<>();
for(char c : s.toCharArray()){
if(c != '#'){
ch.add(c);
}else{
if(ch.size() > 0)
ch.remove(ch.size()-1);
}
}
return String.valueOf(ch);
}
}
**/
Back
|
FazBrowse Home
|
New Git URL