专栏首页Michael阿明学习之路LeetCode 524. 通过删除字母匹配到字典里最长单词(双指针)

LeetCode 524. 通过删除字母匹配到字典里最长单词(双指针)

1. 题目

给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。 如果答案不止一个,返回长度最长字典顺序最小的字符串。如果答案不存在,则返回空字符串。

示例 1:
输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出: 
"apple"

示例 2:
输入:
s = "abpcplea", d = ["a","b","c"]
输出: 
"a"

说明:
所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {	//C++
public:
    string findLongestWord(string s, vector<string>& d) {
    	string ans;
    	int i, j, k;
    	for(i = 0; i < d.size(); ++i)
    	{
    		for(j = k = 0; j <s.size() && k<d[i].size(); ++j)
    		{
    			if(s[j] == d[i][k])//匹配了,移动一位
    				k++;
    		}
    		if(k == d[i].size())//都匹配过了
    		{
    			if(d[i].size() > ans.size())
    				ans = d[i];
    			else if(d[i].size() == ans.size() && d[i] < ans)
    				ans = d[i];
    		}
    	}
    	return ans;
    }
};

148 ms 14.8 MB

class Solution:# py3
    def findLongestWord(self, s: str, d: List[str]) -> str:
        ans = ""
        n = len(d)
        m = len(s)
        for i in range(n):
            j = k = 0
            while j < m and k < len(d[i]):
                if s[j]==d[i][k]:
                    k += 1
                j += 1
            if k==len(d[i]):
                if (len(d[i]) > len(ans)) or (len(d[i])==len(ans) and d[i] < ans):
                    ans = d[i]
        return ans

724 ms 16 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 831. 隐藏个人信息

    定义名称 name 是长度大于等于 2 (length ≥ 2),并且只包含小写字母 a-z 和大写字母 A-Z 的字符串。

    Michael阿明
  • LeetCode 796. 旋转字符串

    A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = ‘abcde’,在移动一次之后结果就是’bcdea’ 。如果在若干次旋转操作之后,A ...

    Michael阿明
  • 程序员面试金典 - 面试题 17.18. 最短超串(双指针+哈希)

    假设你有两个数组,一个长一个短,短的元素均不相同。 找到长数组中包含短数组所有的元素的最短子数组,其出现顺序无关紧要。

    Michael阿明
  • python3 datetime和tim

    文档地址:datetime — Basic date and time types

    py3study
  • Leetcode 5. 最长回文子串

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

    zhipingChen
  • 调度服务 ScheduledExecutorService 经常卡顿问题的排查及解决方法

    如上述代码所示,启动 10 个调度线程,延迟 10 秒,开始执行定时逻辑,然后每隔 2 秒执行一次定时任务。定时任务类为TaskWorker,其要做的事就是根据...

    CG国斌
  • Python基础05 缩进和选择

    缩进 Python最具特色的是用缩进来标明成块的代码。我下面以if选择结构来举例。if后面跟随条件,如果条件成立,则执行归属于if的一个代码块。 先看C语言的表...

    Vamei
  • 一起学Rust-实战leetcode(七)

    判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

    江湖安得便相忘
  • js中判断对象是否为空的三种实现方法

    在写js脚本的时候经常遇到对象为空或者不是对象的情况,出现这种情况我们可以用if去判断它,然后去执行相应的处理方法,具体判断他们的方法有以下几种:

    跟着阿笨一起玩NET
  • Python语句

    >>> range(1, 11, 2) #起始写了表示从起始开始,后面的11不包含,2表示步长值

    py3study

扫码关注云+社区

领取腾讯云代金券