Find substring 'substr' in string 'str'

Question

Jun Jiusi Zheng · Accepted Answer

/**
	 * Jun Zheng, Rice Univ
	 * Find the start index of substring 'substr' in string 'str'
	 * An interview question of Amazon
	 * Java 7, running time O(m+n)
	 * @param str
	 * @param substr
	 * @return
	 */
	private int substringIndex(String str, String substr){
		if(str.length()<1 || substr.length()<1) return -1;
		if(!str.contains(substr)) return -1;
		int i=0;
		for(i=0;i

MT · Answer

A brute-force substring search algorithm checks all possible positions:

1 function Search(string s[1..n], string sub[1..m])
2    for i from 1 to n-m+1
3       for j from 1 to m
4          if s[i+j-1] ? sub[j]
5             jump to next iteration of outer loop
6       return i
7    return

Amazon

Amazon interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches