算法练习之从String.indexOf的模拟实现开始

这篇文章主要介绍了算法练习从String.indexOf的模拟实现开始,需要的朋友可以参考下

String.indexOf的模拟实现，没想象中有多么高深的查找算法，就是最普通的遍历查找

思路：先找到第一个相同的字符，然后依次比较后面的字符，若都相等则表示查找成功

1. /**  
2. * 查找字符串pattern在str中第一次出现的位置  
3. * @param str  
4. * @param pattern  
5. * @return  
6. */ 
7. public int firstIndexOf(String str, String pattern) {  
8. for (int i = 0; i < (str.length() - pattern.length()); i++) {  
9. int j = 0;  
10. while (j < pattern.length()) {  
11. if (str.charAt(i + j) != pattern.charAt(j)) break;  
12. j++;  
13. }  
14. if(j==pattern.length()) return i;  
15. }  
16. return -1;  
17. }  
18.  
19. /**  
20. * 查找字符串pattern在str中最后一次出现的位置  
21. * @param str  
22. * @param pattern  
23. * @return  
24. */ 
25. public int lastIndexOf(String str, String pattern) {  
26. for (int i = str.length() - pattern.length(); i >= 0; i--) {  
27. int j = 0;  
28. while (j < pattern.length()) {  
29. if (str.charAt(i + j) != pattern.charAt(j)) break;  
30. j++;  
31. }  
32. if (j == pattern.length()) return i;  
33. }  
34. return -1;  
35. }  
36.  
37. /**  
38. * 查找字符串pattern在str中出现的位置  
39. * @param str  
40. * @param pattern  
41. * @return  
42. */ 
43. public List<Integer> indexOf(String str, String pattern) {  
44. List<Integer> indexs = new ArrayList<Integer>();  
45. for (int i = 0; i < (str.length() - pattern.length()); i++) {  
46. int j = 0;  
47. while (j < pattern.length()) {  
48. if (str.charAt(i + j) != pattern.charAt(j)) break;  
49. j++;  
50. }  
51. if (j == pattern.length()) indexs.add(i);  
52. }  
53. return indexs;  
54. } 

同样更常用的String.contains方法实际上就是调用的String.indexOf实现

1. /**  
2. * 判断字符串pattern在str中是否存在  
3. * @param str  
4. * @param pattern  
5. * @return  
6. */ 
7. public boolean contains(String str, String pattern) {  
8. return firstIndexOf(str, pattern) != -1;  
9. }