先从简单的算法开始学吧 下面是领扣上刷到的一道字符串查找题(简单难度的)。
题目:对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1(可以不用KMP算法)。
对于刚接触算法的同学来说,确实简单的暴力匹配算法也可能有困难,那下面给大家简单的讲解一下思路 思路:
两个字符串转换成数组char1(source),char2(target); 两个指针(i,j),分别指向这两个数组的索引开始匹配,如果char1[i]==char2[j],则匹配成功,i++,j++比较下一个字符;重新匹配,那么i,j指针应当怎样重新移动呢?举个例子 开始匹配,char1[0]=char2[0],char1[1]=char2[1],但是char1[2]!=char2[2]。所以i要回到索引为1的位置,即i=i-j+1; (这里其实就是i回到0索引的下一个,不懂的画个图就懂啦) 将j置为0;上代码
public int strStr(String source, String target) { // Write your code here char[] char1=source.toCharArray();//用于放source字符串的数组 char[] char2=target.toCharArray();//用于放target字符串的数组 int i=0;//指向source数组的指针 int j=0;//指向target数组的指针 while(i!=char1.length&&j!=char2.length){ if (char1[i]==char2[j]){//两个指针指向的元素相同,则匹配成功 i++; j++; } else{//若这次匹配失败,则进行下一轮 i=i-j+1; j=0;//target数组的指针指向0 } } if(j==char2.length){ return i-j; }else{ return -1; } }