GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — leet-code/Java/Interleaving String.java at master · awangdev/leet-code

Expand file tree

/

Interleaving String.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
executable file
·
211 lines (172 loc) · 6.5 KB
/

Interleaving String.java

Copy path

File metadata and controls

executable file
·
211 lines (172 loc) · 6.5 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
H
1519199180
tags: String, DP
双序列DP, 从最后点考虑.
拆分问题的末尾, 考虑和s1, s2 subsequence之间的关联.
求存在性, boolean
```
/*
LeetCode:
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
*/
/*
Thoughts:
Take continuous part of s1, and part of s2 to form s3.
Consider last index of s3: where is this last char from (s1, or s2)?
Two possible conditioins:
1. s3 last char from s1. Next step: consider s1[0 ~ n-1] and s2 to form s3[0 ~ m - 1];
2. s3 last char from s2. Next step: consider s1 and s2[0 ~ n-1] to form s3[0 ~ m - 1];
dp[i][j]: up to ith and jth index of s1 and s2, is it possible to form s3[i + j];
dp[i][j] = dp[i - 1][j]|s1[i - 1] == s3[i + j - 1] OR dp[i][j - 1]|s2[i - 1] == s3[i + j - 1]
dp[0][0] = false; // 0th length, false;
Time: O(MN)
Space: O(MN)
*/
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s1.length() + s2.length() != s3.length()) {
return false;
}
int m = s1.length();
int n = s2.length();
boolean[][] dp = new boolean[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 && j == 0) { // since s3.length() = s1.length() + s2.length(), so it'll be true here.
dp[i][j] = true;
continue;
}
dp[i][j] = false;
if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
dp[i][j] |= dp[i - 1][j];
}
if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
dp[i][j] |= dp[i][j - 1];
}
}
}
return dp[m][n];
}
}
//Optimize: rolling array
// Time: O(MN), Space O(N)
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s1.length() + s2.length() != s3.length()) {
return false;
}
int m = s1.length();
int n = s2.length();
boolean[][] dp = new boolean[2][n + 1];
int curr = 0;
int prev = 0;
for (int i = 0; i <= m; i++) {
prev = curr;
curr = 1 - prev;
for (int j = 0; j <= n; j++) {
if (i == 0 && j == 0) { // since s3.length() = s1.length() + s2.length(), so it'll be true here.
dp[curr][j] = true;
continue;
}
dp[curr][j] = false;
if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
dp[curr][j] |= dp[prev][j];
}
if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
dp[curr][j] |= dp[curr][j - 1];
}
}
}
return dp[curr][n];
}
}
/*
Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.
Example
For s1 = "aabcc", s2 = "dbbca"
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
Challenge
O(n2) time or better
Tags Expand
Longest Common Subsequence Dynamic Programming
Attempt2: DP[i][j]: boolean that if first S1(i) chars and first S2(j) chars can interleavign first S3(i + j)
Match one char by one char. We have 2 conditions: match s1 or s2 char, Let's do double-for-loop on s1 and s2
1. match s1: s3.charAt(i + j -1) == s1.charAt(i - 1) && DP[i - 1][j]; // makes sure DP[i-1][j] also works before adding s1[i-1] onto the match list
2. match s2: s3.charAt(i + j -1) == s2.charAt(j - 1) && DP[i][j - 1]// similar as above
Note:
Need to initiate the starting conditions with just s1, or just s2
Note2:
DP ususally start i == 1, and always use (i - 1) in the loop... this is all because we are trying to get DP[i][j], which are 1 index more than length
*/
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s3 == null || (s1 == null && s2 == null) || s1.length() + s2.length() != s3.length()) {
return false;
}
boolean[][] DP = new boolean[s1.length() + 1][s2.length() + 1];
DP[0][0] = true; // empty s1 and s2 would be a working case
//with just s1:
for (int i = 1; i <= s1.length(); i++) {
if (s3.charAt(i - 1) == s1.charAt(i - 1) && DP[i - 1][0]) {
DP[i][0] = true;
}
}
//with just s2:
for (int j = 1; j <= s2.length(); j++) {
if (s3.charAt(j - 1) == s2.charAt(j - 1) && DP[0][j - 1]) {
DP[0][j] = true;
}
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if ((s3.charAt(i + j - 1) == s1.charAt(i - 1) && DP[i - 1][j])
|| (s3.charAt(i + j - 1) == s2.charAt(j - 1) && DP[i][j - 1])) {
DP[i][j] = true;
}
}
}
return DP[s1.length()][s2.length()];
}
}
/*
Attempt1, Incorrect: tho, magically passed 91% of lintcode, by coincidence
This solution could goes on and on with s1, and failed at certain point when j == 0 does not fit in.
s1 = "sdfjas;dfjoisdu"
s2 = "dfnakd"
s3 = "sdfjas;dfjoisdf..." // Failed at that 'f' in s3
Thoughts:
DP[mxn]: loop through S1.length and S2.length, record DP[k] = true or false.
DP[k] = (S1(0~i) + S2(0 ~ j)) is leading S3: index of (xxx) == 0.
*/
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s3 == null || (s1 == null && s2 == null) || s1.length() + s2.length() != s3.length()) {
return false;
}
int i = 0;
int j = 0;
String base = "";
for (int k = 0; k < s1.length()*s2.length() - 1; k++) {
if (i < s1.length() || j < s2.length()) {
if (i < s1.length() && s3.indexOf(base + s1.charAt(i)) == 0) {
base += s1.charAt(i);
i++;
} else if (j < s2.length() && s3.indexOf(base + s2.charAt(j)) == 0) {
base += s2.charAt(j);
j++;
} else {
return false;
}
}
}
return true;
}
}
```
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.