【字符串】检查单词是否为句中其他单词的前缀

题目描述

给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。

如果searchWord 是某一个单词的前缀，则返回句子sentence 中该单词所对应的下标（下标从 1 开始）。如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。如果 searchWord 不是任何单词的前缀，则返回 -1 。

字符串 s 的 前缀 是 s 的任何前导连续子字符串。

示例 1：

输入：sentence = "i love eating burger", searchWord = "burg"
输出：4
解释："burg" 是 "burger" 的前缀，而 "burger" 是句子中第 4 个单词。

解题思路 

这是一道简单题，核心就是对字符串进行分割和前缀判断，思路如下：

1. 对字符串进行分割，String strs[] = sentence.split(" ");
2. 遍历字符串数组，如果数组中对元素是使用searchWord作为前缀，则返回这个下标位置+1；

代码实现如下：

 
class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        String strs[] = sentence.split(" ");
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].startsWith(searchWord)) {
                return i + 1;
            }
        }
        return -1;
    }
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPrefixOfWord("i love eating burger", "burg"));
    }
}

接着如果不使用库函数，我自己做字符串处理，思路如下：

• 对字符串进行分割，如果遇到空格则下标加1，记录为count；
• 接着获取字符串并且将这个字符串的每个字符和searchWord的每个字符做比较，如果是前缀则返回count；

注释和代码实现思路如下：

 
class Solution2 {
    public int isPrefixOfWord(String sentence, String searchWord) {
 
        char[] chars = sentence.toCharArray();
 
        // 单词小标从1开始
        int count = 1;
        for (int i = 0; i < chars.length; ) {
 
            // 计算单词的下标
            if (chars[i] == ' ') {
                count++;
                i++;
            }
 
            // 判断是否是前缀
            int temp = i;
            int sameCount = 0;
            for (; i < chars.length && chars[i] != ' '; i++) {
                if (i - temp < searchWord.length() && chars[i] == searchWord.charAt(i - temp)) {
                    sameCount++;
                }
            }
            if (sameCount == searchWord.length()) {
                return count;
            }
 
        }
        return -1;
    }
 
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        System.out.println(solution.isPrefixOfWord("i love eating burger", "burg"));
    }
}

总结

这道题2种解法时间复杂度是O(n)，预期是第二种实现方式耗时更低，因为不用先处理字符串，再做字符串匹配，实际从测试结果来看耗时基本一样。当然如果有更加简洁、高效的思路欢迎回复。