FilesExpand file tree

 master

/

FindSubstring.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

133 lines (109 loc) · 4.56 KB

 master

/

FindSubstring.java

Copy path

Top

File metadata and controls

• Code
• Blame

133 lines (109 loc) · 4.56 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

package Algorithms.string;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

public class FindSubstring {

public static void main(String[] strs) {

String[] L = {"fooo","barr","wing","ding","wing"};

System.out.println(findSubstring("lingmindraboofooowingdingbarrwingmonkeypoundcake", L));

}

public static List<Integer> findSubstring1(String S, String[] L) {

HashMap<String, Integer> map = new HashMap<String, Integer>();

HashMap<String, Integer> found = new HashMap<String, Integer>();

List<Integer> ret = new ArrayList<Integer>();

if (S == null || L == null || L.length == 0) {

return ret;

}

int cntL = 0;

// put all the strings into the map.

for (String s: L) {

if (map.containsKey(s)) {

map.put(s, map.get(s) + 1);

} else {

map.put(s, 1);

cntL++;

}

}

int lenL = L[0].length();

int cntFound = 0;

// 注意这里的条件：i < S.length() - lenL * L.length

// 这里很关键，如果长度不够了，不需要再继续查找

for (int i = 0; i <= S.length() - lenL * L.length; i++) {

// clear the found hashmap.

found.clear();

cntFound = 0;

// 一次前进一个L的length.

// 注意j <= S.length() - lenL; 防止越界

for (int j = i; j <= S.length() - lenL; j += lenL) {

String sub = S.substring(j, j + lenL);

if (map.containsKey(sub)) {

if (found.containsKey(sub)) {

if (found.get(sub) == map.get(sub)) {

// 超过了限制数目

break;

}

found.put(sub, found.get(sub) + 1);

} else {

found.put(sub, 1);

}

if (found.get(sub) == map.get(sub)) {

cntFound++;

}

// L中所有的字符串都已经找到了。

if (cntFound == cntL) {

ret.add(i);

}

} else {

// 不符合条件，可以break,i前进到下一个匹配位置

break;

}

}

}

return ret;

}

// SOLUTION 2:

public static List<Integer> findSubstring(String S, String[] L) {

HashMap<String, Integer> map = new HashMap<String, Integer>();

HashMap<String, Integer> found;

List<Integer> ret = new ArrayList<Integer>();

if (S == null || L == null || L.length == 0) {

return ret;

}

// put all the strings into the map.

for (String s: L) {

if (map.containsKey(s)) {

map.put(s, map.get(s) + 1);

} else {

map.put(s, 1);

}

}

int lenL = L[0].length();

// 注意这里的条件：i < S.length() - lenL * L.length

// 这里很关键，如果长度不够了，不需要再继续查找

for (int i = 0; i <= S.length() - lenL * L.length; i++) {

// 每一次，都复制之前的hashMap.

found = new HashMap<String, Integer>(map);

// 一次前进一个L的length.

// 注意j <= S.length() - lenL; 防止越界

for (int j = i; j <= S.length() - lenL; j += lenL) {

String sub = S.substring(j, j + lenL);

if (found.containsKey(sub)) {

// 将找到字符串的计数器减1.

found.put(sub, found.get(sub) - 1);

// 减到0即可将其移出。否则会产生重复运算，以及我们用MAP为空来判断是否找到所有的单词。

if (found.get(sub) == 0) {

found.remove(sub);

}

} else {

// 不符合条件，可以break,i前进到下一个匹配位置

break;

}

// L中所有的字符串都已经找到了。

if (found.isEmpty()) {

ret.add(i);

}

}

}

return ret;

}

}