-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathIsSubsequence.java
More file actions
143 lines (120 loc) · 4.62 KB
/
IsSubsequence.java
File metadata and controls
143 lines (120 loc) · 4.62 KB
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
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
// https://leetcode.com/problems/is-subsequence/
/*
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none)
of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
Constraints:
0 <= s.length <= 100
0 <= t.length <= 104
s and t consist only of lowercase English letters.
s의 요소가 순서대로 t의 요소에 매핑되는 것이 있는지 확인. O(n^2) 의 경우 100^104으로 값이 커서 불가.
a, h 등 값을 키, index를 value로 저장하는 hash 생성 후 key가 존재하고 key에 매핑되는 index 위치가 이전 index보다 클 경우
s의 각 요소를 가리키는 포인터와 t의 각 요소를 가리키는 포인터를 통해 요소들을 비교하고 s의 요소가 t의 요소에 속하면 각 포인터들을 하나씩 증가시키기
*/
public class IsSubsequence {
String source, target;
int s_length, t_length;
public boolean isSubsequence_1(String s, String t) {
int s_index = 0;
int t_index = 0;
while(s_index < s.length() && t_index < t.length()) {
if(s.charAt(s_index) == t.charAt(t_index)) {
s_index++;
}
t_index++;
}
return s_index == s.length();
}
public boolean isSubsequence_2(String s, String t) {
this.source = s;
this.target = t;
this.s_length = s.length();
this.t_length = t.length();
return rec_isSubsequence(0, 0);
}
public boolean rec_isSubsequence(int s_index, int t_index) {
if (s_index == this.s_length) {
return true;
}
if (t_index == this.t_length) {
return false;
}
if (source.charAt(s_index) == target.charAt(t_index)) {
s_index++;
}
t_index++;
return rec_isSubsequence(s_index, t_index);
}
public boolean isSubsequence_3(String s, String t) {
Integer leftBound = s.length(), rightBound = t.length();
Integer pLeft = 0, pRight = 0;
while (pLeft < leftBound && pRight < rightBound) {
// move both pointers or just the right pointer
if (s.charAt(pLeft) == t.charAt(pRight)) {
pLeft += 1;
}
pRight += 1;
}
return pLeft == leftBound;
}
public boolean isSubsequence_4(String s, String t) {
HashMap<Character, List<Integer>> letterIndicesTable = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
if (letterIndicesTable.containsKey(t.charAt(i))) {
letterIndicesTable.get(t.charAt(i)).add(i);
} else {
ArrayList<Integer> indices = new ArrayList<>();
indices.add(i);
letterIndicesTable.put(t.charAt(i), indices);
}
}
// 소스 문자열 요소 순회 중 일치하는게 없으면 false 모든 요소가 일치하는게 있으면 true
Integer currentMatchIndex = -1;
for (int i = 0; i < s.length(); i++) {
if (!letterIndicesTable.containsKey(s.charAt(i))) {
return false;
}
boolean isMatch = false;
for (Integer index : letterIndicesTable.get(s.charAt(i))) {
if (currentMatchIndex < index) {
currentMatchIndex = index;
isMatch = true;
break;
}
}
if (!isMatch) {
return false;
}
}
return true;
}
public boolean isSubsequence(String s, String t) {
Integer sourceLen = s.length(), targetLen = t.length();
// the source string is empty
if (sourceLen == 0)
return true;
int dp[][] = new int[sourceLen + 1][targetLen + 1];
for (int col = 1; col <= targetLen; col++) {
for (int row = 1; row <=sourceLen; row++) {
if (s.charAt(row - 1) == t.charAt(col - 1)) {
dp[row][col] = dp[row-1][col-1] + 1;
} else {
dp[row][col] = Math.max(dp[row - 1][col], dp[row][col-1]);
}
}
if (dp[sourceLen][col] == sourceLen) {
return true;
}
}
return false;
}
}