admin管理员组

文章数量:1637001

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

in Java, there is an API function name indexof(), it returns index within this string of the first occurrence of the specifiedsubstring. 

java 实现

public String strStr(String haystack, String needle) {
		if(haystack.length()<=0) return null;
        int i = haystack.indexOf(needle);
        if(i==-1) return null;
        else{
        	return haystack.substring(i);
        }
    }

another solution:

public String strStr(String haystack, String needle) {
		if(haystack.length()<=0 && needle.length()>0) return null;
        for(int i=0;i<=haystack.length()-needle.length();i++){
        	boolean flag = true;
        	for(int j=0;j<needle.length();j++){
        		if(haystack.charAt(i+j)!=needle.charAt(j)){
        			flag = false;
        			break;
        		}
        	}
        	if(flag){
    			return haystack.substring(i);
    		}
        }
        return null;
    }

Below two solutions is overkill for interview.

third solution: rolling hash

http://blog.csdn/yanghua_kobe/article/details/8914970

fourth solution: KMP

http://www.ruanyifeng/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html


For c++

strightforward use point scan from begin to end, but this complexity is O(M*N)

char *strStr(char *haystack, char *needle) {
      if(!haystack || !needle) return NULL;
    int hlength = strlen(haystack);
    int nlength = strlen(needle);
    if(hlength<nlength) return NULL;
    for(int i=0; i<hlength-nlength+1;i++){
        char *p = &haystack[i];
        int j=0;
        for(;j<nlength;j++){
            if(*p == needle[j])
                p++;
            else
                break;
        }
        if(j == nlength)
            return &haystack[i];
    }
    return NULL;
    }


the best solution is KMP, complexity is O(N)

本文标签： implementstrStr

版权声明：本文标题：[LeetCode28] Implement strStr() 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1729235666a1191957.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。