【刷题日记】1455. 检查单词是否为句中其他单词的前缀-阿里云开发者社区

【刷题日记】1455. 检查单词是否为句中其他单词的前缀

2023-07-19 87

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【刷题日记】1455. 检查单词是否为句中其他单词的前缀

本次刷题日记的第 103 篇，力扣题为：1455. 检查单词是否为句中其他单词的前缀

一、题目描述：

来刷一道每日一题，1455. 检查单词是否为句中其他单词的前缀

二、这道题考察了什么思想？你的思路是什么？

题目虽然文字不少，但是表达的东西实际上就那么几件事

题目给出 sentence ，是一个字符串，里面是英文句子，用空格将单词进行隔开
题目还给了一个 searchWord 字符串，用来判断 searchWord 是否是 sentence 中的任意单词的前缀
最后要求我们输出在 sentence 中 第一个匹配到 searchWord 前缀的单词位置，单词位置在 sentence 中的位置是从 1 开始的，如果没有匹配到，那就直接返回 -1

分析

看了这道题虽然说是挺简单的，但是我相信会不会有很多兄弟看到题的第一反应是去将 sentence 里面的单词切割出来，放到数组里面，然后进行遍历新的单词数组，逐个与 searchWord 来进行比较呢？

这样子做也不是不行，只不过咱们引入了额外的非常数级别的空间消耗

实际仔细看这个题的要求，并没有存储的要求，咱们直接去遍历题目给出的 sentence ，并且想办法在遍历的过程中将单词切割出来，再与 searchWord 进行匹配一下就可以了

因为，题目要求我们如果 sentence 中有多个都匹配到 searchWord 前缀的单词，那么取第一个，因此实际上，我们找到一个就不用往后找了，则咱们直接从 sentence 头进行遍历即可

就图中可以知道，咱们获取单词的方式，同理，其他的单词获取方式也是如此，对于判断某个单词的前缀是否是 searchWord ，咱们可以直接调用库函数，也可以自己写

判断前缀的时候，只有当 searchWord 和单词的前 len(单词) 个字符对应相等的时候，我们才能判断 searchWord 是单词的前缀，其余情况，咱们一律不算

那么，接下来就用上述说道的双指针的方式来手撸代码吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

遍历 sentence
获取到每一个单词（记录单词的 start and end 指针即可）
判断 searchWord 是否是单词的前缀，如果是则返回具体的单词位置，如果不是则继续遍历

对于判断前缀，我们可以使用 golang 的 strings.HasPrefix() 函数，当然也可以自定一个判断前缀的函数都是可以的，看自己的需求和想法了

编码如下：

func isPrefixOfWord(sentence string, searchWord string) int {
    // 简单使用双指针的方式，减少空间复杂度
    index := 1  // 标识单词的位置
    n := len(sentence)
    for i:=0; i<n; i++ {
        // 单词的起始位置
        start := i 
        for i<n && sentence[i] != ' '{
            i++
        }
        // 判断到当前 i 索引对应的值为 空格，即一个单词的分割点
        end := i
        // 开始判断 searchWord 是否是 上述单词的前缀
        // if strings.HasPrefix(sentence[start:end], searchWord)
        if myHasPrefix(sentence[start:end], searchWord) {
            return index
        }
        index++
    }
    return -1
}
func myHasPrefix(nums string, str string)bool{
    nLength := len(nums)
    mLength := len(str)
    if nLength == 0 || mLength == 0 {
        return false
    }
    i := 0
    for i< nLength && i<mLength{
        if nums[i] != str[i]{
            return false
        }
        i++
    }
    if i == mLength{
        return true
    }
    return false
}
四