文章目录
一、字符串查找
二、蛮力算法代码示例
一、字符串查找
算法题目链接 : https://www.lintcode.com/problem/13/
在 一个字符串 中查找 另外一个字符串 第一次出现的位置 ;
如 : 在 “abcdefghijk” 中查找 “def” 第一次出现的位置 , 是 4 44 ;
该方法使用 暴力算法 , 两层 for 循环 , 肯定可以解决 ; 如果用暴力算法 , 那面试基本就凉了 ; 暴力算法的复杂度是 O ( m × n ) O(m \times n)O(m×n) , m mm 是第一个大字符串的长度 , n nn 是被查找的字符串长度 ;
KMP 算法 是专门用于解决该问题的算法 , 该算法 只能用于解决在一个字符串中查找另外一个字符串的问题 ; KMP 算法主要靠背诵 , 没有涉及到算法的理论 , 只能用于解决单一字符串查找问题 , 一般面试时不考虑使用该算法 ; KMP 算法的算法复杂度是 O ( m + n ) O(m + n)O(m+n) ;
Rabin-Karp 算法 比 KMP 算法更简单 , 其基本原理就是比较字符串的 哈希码 ( HashCode ) , 快速的确定子字符串是否等于被查找的字符串 ;
二、蛮力算法代码示例
蛮力算法 :
需要进行双层循环遍历 ;
外层循环 遍历 source 字符串 , 遍历 source.length() - target.length() 次 ,
假设被遍历的索引 i 开始 , target.length() 位字符串 与 target 字符串是否相等 ,
如果相等 , 则该索引就是题目中想要的结果 ,
如果不相等 , 那么继续遍历下一个索引 ;
内层循环 就是遍历 target 字符串 , 逐位对比 两个字符串是否相等 ;
代码 :
class Solution { /** * 蛮力算法 : 双层循环, 外层循环循环 source, 内层循环循环 target 对应字符是否相等 * @param source:在该字符串中查找子字符串 * @param target:被查找的字符串 * @return: return the index */ public int strStr(String source, String target) { if (target == null || "".equals(target)) { return 0; } for (int i = 0; i < source.length() - target.length() + 1; i++) { boolean notEqual = false; for (int j = 0; j < target.length(); j++) { if (source.charAt(i + j) != target.charAt(j)) { // 只要有一个字符不相等, 就说明遍历的该子字符串不匹配 notEqual = true; break; } } // 如果所有的字符都匹配, 即对比中没有不相等的字符, 该 i 索引就是结果 if (!notEqual) { return i; } } return -1; } } class Main { public static void main(String[] args) { int index = new Solution().strStr("mabcban", "cb"); System.out.println(index); } }
