前缀和+后缀和算法模板-附LeetCode习题-面试题 01.05. 一次编辑

简介: 前缀和+后缀和算法模板-附LeetCode习题-面试题 01.05. 一次编辑

面试题 01.05. 一次编辑


难度中等142收藏分享切换为英文接收动态反馈


字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。


示例 1:


输入:

first = "pale"

second = "ple"

输出: True

示例 2:


输入:

first = "pales"

second = "pal"

输出: False

通过次数47,199提交次数142,718


解题思路:

如果两个字符串符合要求,那么他的前缀和 and 后缀和应该是相等的。


Python代码:

 

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        p1 , p2 , q1 , q2 = 0 , 0 , len(first)-1 , len(second)-1
        while p1<=q1 and p2<=q2:
            if first[p1]==second[p2]:
                p1 += 1
                p2 += 1
                continue
            elif first[q1]==second[q2]:
                q1 -= 1
                q2 -= 1
            else: break
        return q1-p1 + q2-p2<=0 and abs(p1-p2)<=1 and abs(q1-q2)<=1

C++代码:

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int p1 = 0 , p2 = 0;
        int q1 = first.size()-1 , q2 = second.size()-1;
        while (p1<=q1 && p2<=q2)
        {
            if (first[p1]==second[p2]){
                p1++;
                p2++;
                continue;
            }
            else if (first[q1] == second[q2]){
                q1--;
                q2--;
            }
            else break;
        }
        return q1-p1 + q2-p2 <=0 && abs(p2-p1)<=1 && abs(q2-q1)<=1;
    }
};

python的快速解法:

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        m , n = len(first) , len(second)
        if m-n>1:return False
        if m<n:return self.oneEditAway(second , first)
        for i , (x , y) in enumerate(zip(first , second)):
           if x!=y:
               return first[i+1:]==second[i+1:] if m==n else first[i+1:]==second[i:]
        return True
相关文章
|
11月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
106 0
|
6月前
|
算法 安全 搜索推荐
套用算法模板备案审核问题增多的原因及解决建议
随着算法备案要求的完善,企业常因使用网上廉价模板而遭遇审核通过率低、问题增多的困境。本文分析了审核不通过的原因,包括模板缺乏针对性、审核标准严格、审核人员主观差异及企业准备不足等,并提出建议:深入了解备案要求、准备详尽材料、避免通用模板、寻求专业帮助。备案后还需持续合规管理,确保算法服务安全运行。
|
算法
【算法】前缀和——二维前缀和模板题
【算法】前缀和——二维前缀和模板题
106 0
|
7月前
|
人工智能 编解码 算法
使用 PAI-DSW x Free Prompt Editing图像编辑算法,开发个人AIGC绘图小助理
使用 PAI-DSW x Free Prompt Editing图像编辑算法,开发个人AIGC绘图小助理
128 0
|
8月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
257 3
|
11月前
|
机器学习/深度学习 人工智能 自然语言处理
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
阿里云人工智能平台 PAI 团队发表的图像编辑算法论文在 MM2024 上正式亮相发表。ACM MM(ACM国际多媒体会议)是国际多媒体领域的顶级会议,旨在为研究人员、工程师和行业专家提供一个交流平台,以展示在多媒体领域的最新研究成果、技术进展和应用案例。其主题涵盖了图像处理、视频分析、音频处理、社交媒体和多媒体系统等广泛领域。此次入选标志着阿里云人工智能平台 PAI 在图像编辑算法方面的研究获得了学术界的充分认可。
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
|
10月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
204 4
|
10月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
11月前
|
机器学习/深度学习 人工智能 算法
【MM2024】面向 StableDiffusion 的多目标图像编辑算法 VICTORIA
阿里云人工智能平台 PAI 团队与华南理工大学合作在国际多媒体顶级会议 ACM MM2024 上发表 VICTORIA 算法,这是一种面向 StableDiffusion 的多目标图像编辑算法。VICTORIA 通过文本依存关系来修正图像编辑过程中的交叉注意力图,从而确保关系对象的一致性,支持用户通过修改描述性提示一次性编辑多个目标。
|
11月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
104 2

热门文章

最新文章