admin管理员组文章数量:1636935
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
Goal: Determine whether needle is substring of haystack or not &
return the substring(i) i is first occurrence of needle in haystack
Idea: Use KMP algorithm is an optimal Approach to solve this problem
but since there is no time complexity requirement in problem.
Approach:
we can use brute force approach instead.
Check match in haystack with needle every time in lengt of needle using
nested for loop + boolean variable as a checker to skip unmatched
Time Complexity: O(n*m)
Space: O(1)
public class Solution {
public String strStr(String haystack, String needle) {
if(needle.length()==0) return haystack;
int hLen=haystack.length();
int nLen=needle.length();
if(nLen>hLen){ return null;}
for(int i=0;i<=hLen-nLen;i++){
boolean checker=true;
//check the subString in length of needle
for(int j=0;j<nLen;j++){
//skip it if they are unmatched
if(haystack.charAt(i+j)!=needle.charAt(j)){
checker=false;
break;
}
}
if(checker){
return haystack.substring(i);
}
}
return null;
}
}
版权声明:本文标题:Implement strStr() Java 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729235360a1191929.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论