leetcode 524. 通过删除字母匹配到字典里最长单词

leetcode[524] 通过删除字母匹配到字典里最长单词

#include <iostream>
#include <string>
#include <vector>
using std::vector;
using std::string;

/*
 * @lc app=leetcode.cn id=524 lang=cpp
 *
 * [524] 通过删除字母匹配到字典里最长单词
 */

// @lc code=start
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string res = "";
        for(string t : dictionary){
            int i =0,j = 0;
            while(i < t.length() && j < s.length()){
                if(t[i] == s[j]){
                    ++ i;
                }
                ++ j;
            }
            if(i == t.length()){
                if(t.length() > res.length() || (t.length() == res.length() && t < res)){
                    res = t;
                }
            }
        }
        return res;
    }
};
// @lc code=end

int main() {
    Solution solution;
    string s = "abpcplea";
    vector<string> d = {"ale", "apple", "monkey", "plea"};
    string result = solution.findLongestWord(s, d);
    std::cout << "The longest word is: " << result << std::endl;
    return 0;
}
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

代码解析

包含头文件

#include <iostream>
#include <string>
#include <vector>
1
2
3

• #include <iostream>: 用于输入输出操作。
• #include <string>: 用于处理字符串。
• #include <vector>: 用于处理动态数组（向量）。

使用命名空间中的类型

using std::vector;
using std::string;
1
2

• 这样做可以简化代码，不用在每次使用 vector 和 string 时都加上 std:: 前缀。

定义 Solution 类和 findLongestWord 方法

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string res = "";
        for(string t : dictionary){
            int i = 0, j = 0;
            while(i < t.length() && j < s.length()){
                if(t[i] == s[j]){
                    ++i;
                }
                ++j;
            }
            if(i == t.length()){
                if(t.length() > res.length() || (t.length() == res.length() && t < res)){
                    res = t;
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

findLongestWord 方法详解

• 参数:

  • s: 一个字符串，需要从中删除一些字符以匹配字典中的单词。
  • dictionary: 一个字符串向量，包含所有可能的单词。

• 局部变量:

  • res: 用于存储符合条件的最长单词，初始化为空字符串。

• 遍历字典:

  for(string t : dictionary){
  1

  遍历字典中的每个单词 t。

• 双指针匹配:

  int i = 0, j = 0;
  while(i < t.length() && j < s.length()){
      if(t[i] == s[j]){
          ++i;
      }
      ++j;
  }
  1
  2
  3
  4
  5
  6
  7

  • i 用于遍历单词 t，j 用于遍历字符串 s。
  • 如果 t[i] == s[j]，则指针 i 和 j 都向前移动；否则，只移动 j。
  • 这样做是为了判断单词 t 是否可以通过删除 s 中的某些字符得到。

• 检查匹配结果:

  if(i == t.length()){
      if(t.length() > res.length() || (t.length() == res.length() && t < res)){
          res = t;
      }
  }
  1
  2
  3
  4
  5

  • 如果 i == t.length()，表示 t 的所有字符都在 s 中找到且顺序一致。
  • 检查 t 是否比当前 res 更长，或者长度相等但字典序更小。如果是，更新 res。

main 函数

int main() {
    Solution solution;
    string s = "abpcplea";
    vector<string> d = {"ale", "apple", "monkey", "plea"};
    string result = solution.findLongestWord(s, d);
    std::cout << "The longest word is: " << result << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8

• 创建 Solution 类的对象 solution。
• 定义字符串 s 和字符串向量 d。
• 调用 findLongestWord 方法获取结果。
• 输出结果。

运行代码时，输出应该是：

The longest word is: apple
1

LeetCode第524题“通过删除字母匹配到字典里最长单词”的题目要求是：给定一个字符串 s 和一个字符串字典 d，找到字典 d 中最长的字符串，这个字符串可以通过删除 s 中的一些字符得到。如果有多个结果，返回字典顺序最小的那个字符串。

下面是C++实现代码：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        string longest = "";
        for (string word : d) {
            if (isSubsequence(word, s)) {
                if (word.length() > longest.length() || (word.length() == longest.length() && word < longest)) {
                    longest = word;
                }
            }
        }
        return longest;
    }

private:
    bool isSubsequence(string x, string y) {
        int i = 0, j = 0;
        while (i < x.length() && j < y.length()) {
            if (x[i] == y[j]) {
                i++;
            }
            j++;
        }
        return i == x.length();
    }
};

int main() {
    Solution solution;
    string s = "abpcplea";
    vector<string> d = {"ale", "apple", "monkey", "plea"};
    string result = solution.findLongestWord(s, d);
    cout << "The longest word is: " << result << endl;
    return 0;
}
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

解释：

1. findLongestWord 函数：

   • 遍历字典中的每个单词，检查它是否是字符串 s 的子序列。
   • 如果当前单词是 s 的子序列，并且比当前记录的最长单词更长，或者长度相同但字典序更小，则更新最长单词。

2. isSubsequence 函数：

   • 该函数用于检查一个单词 x 是否是另一个单词 y 的子序列。
   • 使用两个指针分别遍历 x 和 y，如果 x 中的字符在 y 中按顺序出现，则 x 是 y 的子序列。

3. 主函数：

   • 创建一个 Solution 对象，并初始化字符串 s 和字典 d。
   • 调用 findLongestWord 函数找到结果并输出。

测试：

运行代码时，输出应该是：

The longest word is: apple
1

这个解决方案遍历字典中的每个单词并检查它是否是字符串 s 的子序列，时间复杂度为 O(n*m)，其中 n 是字典的大小，m 是字符串 s 的长度。