Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

1813. Sentence Similarity III

給兩個sentence，sentence裡每個單字是由1個空格隔開的

請問是否可以藉由往其中一個sentence中插入一個新的sentence

使2個sentence相同

可以回傳true

反之false

思路:

假設s1單字數比s2少

那麼有3種情況可以達成題目所需

假設新的sentence為s3

(1)s1 + s3=s2

(2)s3 + s1=s2

(3)s1_1 + s3 +s1_2 = s2 其中 s1_1 + s1_2=s1

上述3種情況可以得出一個結論

s1的開頭或結尾的單字會跟s2重疊

所以我們就從s1、s2第一個單字跟最後一個單字

去比對相同的數目

如果相同的數量 >= s1的單字數

就回傳true

反之回傳false

golang code :

func areSentencesSimilar(sentence1 string, sentence2 string) bool {
        s1 := strings.Split(sentence1, " ")
        s2 := strings.Split(sentence2, " ")
        if len(s1) > len(s2) {
                s1, s2 = s2, s1
        }
        n,m := len(s1),len(s2)
        start, end := 0, 0
        for start < n && s1[start] == s2[start] {
                start++
        }
        for n-1-end > -1 && s1[n-1-end] == s2[m-1-end] {
                end++
        }
        return end+start >= n
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.5 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728208398.A.A21.html
推 oin1104: 我好崇拜你
推 EliteCaterpi: 什麼時候要送芋圓模型？
推 sustainer123: 大師
→ PogChampLUL: 大師
推 Sougou: 大師
推 dont: 大師