假设我们有一个字符串和一个字符串字典,我们必须在字典中找到最长的字符串,该字符串可以通过删除给定字符串的某些字符来形成。如果有多个可能的结果,则仅以最小的字典顺序返回最长的单词。如果没有结果,则返回一个空白字符串。因此,如果输入类似于“ abpcplea”,并且d = [“ ale”,“ apple”,“ monkey”,“ plea”],则结果将为“ apple”。
为了解决这个问题,我们将遵循以下步骤-
定义一个称为的方法isSubsequence()
。这将需要s1和s2
j:= 0
对于范围从0到s1的i
如果s2 [j] = s1 [i],则将j增加1
如果j = s2的大小,则打破循环
如果j = s2的大小,则返回true
从主要方法中,执行以下操作-
ans:=一个空白字符串
对于范围从0到d – 1的i
如果isSubsequence(s,x)为true,则ans:= x
x:= d [i]
如果x的大小> ans的大小或x的大小= ans的大小且x <ans的大小,则
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isSubsequence(string s1, string s2){ int j =0; for(int i = 0; i < s1.size(); i++){ if(s2[j] == s1[i]){ j++; if(j == s2.size()) break; } } return j == s2.size(); } string findLongestWord(string s, vector<string>& d) { string ans = ""; for(int i = 0; i < d.size(); i++){ string x = d[i]; if(x.size() > ans.size() || (x.size() == ans.size() && (x < ans))){ if(isSubsequence(s, x)) ans = x; } } return ans; } }; main(){ vector<string> v = {"ale","apple","monkey","plea"}; Solution ob; cout << (ob.findLongestWord("abpcplea", v)); }
"abpcplea" ["ale","apple","monkey","plea"]
输出结果
apple