LintCode 13. strStr 原创Java参考解答

LintCode 13. strStr 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/strstr/

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Clarification

Do I need to implement KMP Algorithm in a real interview?

  • Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure your confirm with the interviewer first.

Example

If source = "source" and target = "target", return -1.

If source = "abcdabcdefg" and target = "bcd", return 1.

解题思路

题目是求字符串target在字符串source中出现的位置。

  • 先检查输入的合理性,source、target是否为空,为空则返回-1。
  • 二重循环,比较source每个位置开始能否完整地走完target的每一个字符。

参考代码

class Solution { 
    /** 
     * Returns a index to the first occurrence of target in source, 
     * or -1  if target is not part of source. 
     * @param source string to be scanned. 
     * @param target string containing the sequence of characters to match. 
     */ 
    public int strStr(String source, String target) { 
        if (source == null || target == null) { 
            return -1; 
        } 
 
        for (int i = 0; i < source.length() - target.length() + 1; i++) { 
            int j; 
            for (j = 0; j < target.length(); j++) { 
                if (source.charAt(i + j) != target.charAt(j)) { 
                    break; 
                } 
            } 
            if (j == target.length()) { 
                return i; 
            } 
        } 
         
        return -1; 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。