5706. 句子相似性III（第49场双周赛）

发表于 更新于 分类于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目描述

一个句子是由一些单词与它们之间的单个空格组成，且句子的开头和结尾没有多余空格。比方说，"Hello World" ，"HELLO" ，"hello world hello world" 都是句子。每个单词都 只 包含大写和小写英文字母。

如果两个句子 sentence1 和 sentence2 ，可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一个句子，那么我们称这两个句子是 相似的 。比方说，sentence1 = "Hello my name is Jane" 且 sentence2 = "Hello Jane" ，我们可以往 sentence2 中 "Hello" 和 "Jane" 之间插入 "my name is" 得到 sentence1 。

给你两个句子 sentence1 和 sentence2 ，如果 sentence1 和 sentence2 是相似的，请你返回 true ，否则返回 false 。

示例 1：

1
2
3
>输入：sentence1 = "My name is Haley", sentence2 = "My Haley"
>输出：true
>解释：可以往 sentence2 中 "My" 和 "Haley" 之间插入 "name is" ，得到 sentence1 。

示例 2：

1
2
3
>输入：sentence1 = "of", sentence2 = "A lot of words"
>输出：false
>解释：没法往这两个句子中的一个句子只插入一个句子就得到另一个句子。

示例 3：

1
2
3
>输入：sentence1 = "Eating right now", sentence2 = "Eating"
>输出：true
>解释：可以往 sentence2 的结尾插入 "right now" 得到 sentence1 。

示例 4：

1
2
>输入：sentence1 = "Luky", sentence2 = "Lucccky"
>输出：false

提示：

  • 1 <= sentence1.length, sentence2.length <= 100
  • sentence1 和 sentence2 都只包含大小写英文字母和空格。
  • sentence1 和 sentence2 中的单词都只由单个空格隔开。

题解

本题我采用了动态规划的思路。果然还是很不熟练，找状态转移方程想了好久，想出来的还是感觉很笨的办法，果然还是得加强练习。

思路：dp[i, j]表示sentence1的前i个和sentence2的前j个word能否经过一次插入获得。分别考虑两个句子当前的word是否是可以插入另一个sentence获得相同的sentence。情况如下：

  1. 如果sentence1前i-1个word和sentence2前j个word可以通过一次插入相等，并且之前插入的word在sentence1中并且还可以继续插入，那么就可以继续在sentence1中插入，我们记为1。
  2. 如果sentence1前i个word和sentence2前j-1个word可以通过一次插入相等，并且之前插入的word在sentence2中并且还可以继续插入，那么就可以继续在sentence2中插入，我们记为2。
  3. 以上两种情况都不符合，如果sentence1第i个word和sentence2第j个word一致，那么我们只需要考虑sentence1前i-1个word和sentence2前j-1个word是否可以通过一次插入相等。如果之前是在继续插入的，那么我们现在就要终止插入，记为3，否则dp[i, j]=dp[i-1, j-1]。（这里我们已经排除了虽然当前word相等但是可以把当前的word当成插入的情况：比如sentence1=”a b c“, sentence2="a b g b c"中sentence2中的"g b"是插入的，而sentence1 中也存在b）
  4. 剩下的情况就是我们无法插入一个sentence使两组sentence相等，记为4

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 首先将sentence转化为word数组
char** sentenceToWord(char * sentence, int *wordlen) {
    int sen_len = strlen(sentence);
    if (sen_len == 0) return NULL;
    char** word = (char**)malloc(sizeof(char*) * sen_len);
    int wordIdx = 0, i = 0, charIdx = 0;
    word[wordIdx] = (char*)malloc(sizeof(char) * (sen_len+1));
    for (; i < sen_len; i++) {
        if (sentence[i] == ' ') {
            word[wordIdx][charIdx] = '\0'; 
            word[++wordIdx] = (char*)malloc(sizeof(char) * sen_len);
            charIdx = 0;
        } else {
            word[wordIdx][charIdx++] = sentence[i];
        }
    }
    word[wordIdx][charIdx] = '\0';
    *wordlen = wordIdx + 1;
    return word;
}

bool areSentencesSimilar(char * sentence1, char * sentence2){
    int len1, len2;
    char** word1 = sentenceToWord(sentence1, &len1);
    char** word2 = sentenceToWord(sentence2, &len2);
    int i, j;
    int ** dp = (int**)malloc(sizeof(int*) * (len1+1));
    for (i = 0; i <= len1; i++) dp[i] = (int*)malloc(sizeof(int) * (len2 + 1));
    // 0代表还没有插入
    // 1代表i正在插入
    // 2代表j正在插入
    // 3代表已经插入
    // 4代表无法插入
    dp[0][0] = 0;
    for (i = 1; i <= len1; i++) dp[i][0] = 1;
    for (i = 1; i <= len2; i++) dp[0][i] = 2;
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (dp[i-1][j] == 1 || dp[i-1][j] == 0) dp[i][j] = 1;
            else if (dp[i][j-1] == 2 || dp[i][j-1] == 0) dp[i][j] = 2;
            else if (!strcmp(word1[i-1], word2[j-1])) {
                if (dp[i-1][j-1] == 1 || dp[i-1][j-1] == 2) dp[i][j] = 3;
                else dp[i][j] = dp[i-1][j-1];
            }
            else {
                dp[i][j] = 4;
            }
        }
    }
    return dp[len1][len2] != 4;
}