学校网站建设电话,上海有名网站建站开发公司,补习吧 一家专门做家教的网站,商河 网站建设问题描述
给定两个字符串 haystack 和 needle#xff0c;我们需要在 haystack 中找出 needle 字符串的第一个匹配项的下标。如果 needle 不是 haystack 的一部分#xff0c;则返回 -1。
暴力搜索算法
暴力搜索算法是一种简单直观的字符串匹配方法。它的基本思想是#xf…问题描述
给定两个字符串 haystack 和 needle我们需要在 haystack 中找出 needle 字符串的第一个匹配项的下标。如果 needle 不是 haystack 的一部分则返回 -1。
暴力搜索算法
暴力搜索算法是一种简单直观的字符串匹配方法。它的基本思想是从 haystack 的每个可能的起始位置开始检查是否有与 needle 相匹配的子串。
算法步骤
检查空字符串如果 needle 是空字符串根据题意返回 0。获取长度获取 needle 和 haystack 的长度。遍历 haystack遍历 haystack对于每个可能的起始位置使用内层循环检查 needle 是否匹配。字符比较在内层循环中比较 haystack 的子串和 needle 的每个字符。返回结果如果找到匹配项返回匹配项的下标如果遍历完 haystack 都没有找到匹配项返回 -1。
Java 实现
以下是使用暴力搜索算法解决字符串匹配问题的 Java 实现 java
class Solution {public int strStr(String haystack, String needle) {// 如果needle为空字符串根据题意返回0if (needle.isEmpty()) return 0;// 获取needle和haystack的长度int m needle.length();int n haystack.length();// 遍历haystackfor (int i 0; i n - m; i) {// 从当前位置开始比较needle和haystack的子串是否相等for (int j 0; j m; j) {// 如果不相等跳出内层循环继续外层循环if (haystack.charAt(i j) ! needle.charAt(j)) {break;}// 如果相等继续比较下一个字符if (j m - 1) {return i; // 如果比较完needle的最后一个字符说明找到了匹配项返回下标}}}// 如果遍历完haystack都没有找到匹配项返回-1return -1;}
}
代码解释
处理特殊情况如果 needle 是空字符串根据题意返回 0。获取长度获取 needle 和 haystack 的长度。遍历 haystack使用外层循环遍历 haystack内层循环遍历 needle。字符比较在内层循环中比较 haystack 的当前子串和 needle 的每个字符。返回结果如果找到匹配项返回匹配项的下标如果遍历完 haystack 都没有找到匹配项返回 -1。
