FilesExpand file tree

 master

/

392_IsSubsequence392.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

80 lines (75 loc) · 2.33 KB

 master

/

392_IsSubsequence392.java

Copy path

Top

File metadata and controls

• Code
• Blame

80 lines (75 loc) · 2.33 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

/**

* Given a string s and a string t, check if s is subsequence of t.

*

* You may assume that there is only lower case English letters in both s and t.

* t is potentially a very long (length ~= 500,000) string, and s is a short

* string (<=100).

*

* A subsequence of a string is a new string which is formed from the original

* string by deleting some (can be none) of the characters without disturbing

* the relative positions of the remaining characters. (ie, "ace" is a

* subsequence of "abcde" while "aec" is not).

*

* Example 1:

* s = "abc", t = "ahbgdc"

* Return true.

*

* Example 2:

* s = "axc", t = "ahbgdc"

* Return false.

*

* Follow up:

* If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you

* want to check one by one to see if T has its subsequence. In this scenario,

* how would you change your code?

*/

public class IsSubsequence392 {

public boolean isSubsequence(String s, String t) {

if (s == null && t == null) return true;

if (s == null || t == null) return true;

int lenS = s.length();

int lenT = t.length();

char[] charS = s.toCharArray();

char[] charT = t.toCharArray();

int i = 0;

int j = 0;

while (i < lenS && j < lenT) {

while (j < lenT && charT[j] != charS[i]) {

j++;

}

if (j == lenT) break;

j++;

i++;

}

return i == lenS;

}

/**

* https://leetcode.com/problems/is-subsequence/discuss/87297/Java.-Only-2ms.-Much-faster-than-normal-2-pointers.

*/

public boolean isSubsequence2(String s, String t) {

if(t.length() < s.length()) return false;

int prev = 0;

for(int i = 0; i < s.length();i++) {

char tempChar = s.charAt(i);

prev = t.indexOf(tempChar,prev);

if(prev == -1) return false;

prev++;

}

return true;

}

public boolean isSubsequence3(String s, String t) {

int i = 0;

int j = 0;

char[] chars = s.toCharArray();

char[] chart = t.toCharArray();

while (i < chars.length && j < chart.length) {

if (chars[i] == chart[j]) {

i++;

j++;

} else {

j++;

}

}

return i == chars.length;

}

}