算法练习之从String.indexOf的模拟实现开始
时间：2021-01-09 11:15:10|栏目：.NET代码|点击： 次
String.indexOf的模拟实现，没想象中有多么高深的查找算法，就是最普通的遍历查找
思路：先找到第一个相同的字符，然后依次比较后面的字符，若都相等则表示查找成功
/**
* 查找字符串pattern在str中第一次出现的位置
* @param str
* @param pattern
* @return
*/
public int firstIndexOf(String str, String pattern) {
for (int i = 0; i < (str.length() - pattern.length()); i++) {
int j = 0;
while (j < pattern.length()) {
if (str.charAt(i + j) != pattern.charAt(j)) break;
j++;
}
if(j==pattern.length()) return i;
}
return -1;
}
/**
* 查找字符串pattern在str中最后一次出现的位置
* @param str
* @param pattern
* @return
*/
public int lastIndexOf(String str, String pattern) {
for (int i = str.length() - pattern.length(); i >= 0; i--) {
int j = 0;
while (j < pattern.length()) {
if (str.charAt(i + j) != pattern.charAt(j)) break;
j++;
}
if (j == pattern.length()) return i;
}
return -1;
}
/**
* 查找字符串pattern在str中出现的位置
* @param str
* @param pattern
* @return
*/
public List<Integer> indexOf(String str, String pattern) {
List<Integer> indexs = new ArrayList<Integer>();
for (int i = 0; i < (str.length() - pattern.length()); i++) {
int j = 0;
while (j < pattern.length()) {
if (str.charAt(i + j) != pattern.charAt(j)) break;
j++;
}
if (j == pattern.length()) indexs.add(i);
}
return indexs;
}
同样更常用的String.contains方法实际上就是调用的String.indexOf实现
/**
* 判断字符串pattern在str中是否存在
* @param str
* @param pattern
* @return
*/
public boolean contains(String str, String pattern) {
return firstIndexOf(str, pattern) != -1;
}
