题目
给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串。
示例 1:
输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"
示例 2:
输入:
s = "abpcplea", d = ["a","b","c"]
输出:
"a"
说明:
所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。
解析
1.依次从d中取出字符,并与s进行对比,若d[i][m] == s[n]则继续遍历,否则,n++;直到m == d[i].Length,若m < d[i].Length说明不是合法字串
2.此时判断是不是最长字符串,若是则替换,若不是,则继续遍历
3.若两个字串长度相等,则对比字符串的字符大小
public string FindLongestWord(string s, IList<string> d) {
string longStr = "";
int longLen = -1;
for (int i = 0; i < d.Count; i++)
{
string temp = d[i];
int m = 0, n = 0;
while (m < s.Length && n < temp.Length)
{
if (s[m] == temp[n]) n++;
m++;
}
//d[i]到了最后一个字符,则说明,d[i]是s删除某些字符后的一个字串
if (n == temp.Length)
{
if (n > longLen)
{
longLen = n;
longStr = temp;
}
else if(longLen == n)
{
longStr = CompareStr(longStr, temp);
}
}
}
return longStr;
}
string CompareStr(string a, string b)
{
int i = 0;
while (i < a.Length)
{
if (a[i] - '0' < b[i] - '0') return a;
return b;
}
return "";
}
网友评论