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

题目

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”]
输出：“apple”

示例 2：

输入：s = “abpcplea”, dictionary = [“a”,”b”,”c”]
输出：“a”

提示：

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s 和 dictionary[i] 仅由小写英文字母组成

  思路

  暴力求解。
  对于dictionary~i~，按照顺序与s进行比较，看看dictionary~i~在s中是否能够按顺序都找到。如果能找到，就比较长度，长度相等则比较字典序。

  代码

  class Solution {
  public:
      string findLongestWord(string s, vector<string>& dictionary) {
          int res_id = -1;
          for(int i=0;i<dictionary.size();++i){
              if(dictionary[i].length()>s.length()) continue;
              int j=0;
              for(int k=0;k<s.size();++k){
                  if(s[k]==dictionary[i][j]) j++;
              }
              if(j!=dictionary[i].length()) continue;
              if(res_id==-1||
              dictionary[i].length()>dictionary[res_id].length()||
              (dictionary[i].length()==dictionary[res_id].length()&&dictionary[i]<dictionary[res_id])){
                  res_id = i;
              }
          }
          if(res_id==-1) return "";
          return dictionary[res_id];
      }
  };