C++实现LeetCode(161.一个编辑距离)

[LeetCode] 161. One Edit Distance 一个编辑距离

Given two strings s and t, determine if they are both one edit distance apart.

Note: 

There are 3 possiblities to satisify one edit distance apart:

  1. Insert a character into s to get t
  2. Delete a character from s to get t
  3. Replace a character of s to get t

Example 1:

Input: s = "ab", t = "acb" Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "cab", t = "ad"

Output: false

Explanation: We cannot get t from s by only one step.

Example 3:

Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.

这道题是之前那道 Edit Distance 的拓展，然而这道题并没有那道题难，这道题只让我们判断两个字符串的编辑距离是否为1，那么只需分下列三种情况来考虑就行了：

1. 两个字符串的长度之差大于1，直接返回False。

2. 两个字符串的长度之差等于1，长的那个字符串去掉一个字符，剩下的应该和短的字符串相同。

3. 两个字符串的长度之差等于0，两个字符串对应位置的字符只能有一处不同。

分析清楚了所有的情况，代码就很好写了，参见如下：

解法一：

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() < t.size()) swap(s, t);
        int m = s.size(), n = t.size(), diff = m - n;
        if (diff >= 2) return false;
        else if (diff == 1) {
            for (int i = 0; i < n; ++i) {
                if (s[i] != t[i]) {
                    return s.substr(i + 1) == t.substr(i);
                }
            }
            return true;
        } else {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                if (s[i] != t[i]) ++cnt;
            }
            return cnt == 1;
        }
    }
};

我们实际上可以让代码写的更加简洁，只需要对比两个字符串对应位置上的字符，如果遇到不同的时候，这时看两个字符串的长度关系，如果相等，则比较当前位置后的字串是否相同，如果s的长度大，那么比较s的下一个位置开始的子串，和t的当前位置开始的子串是否相同，反之如果t的长度大，则比较t的下一个位置开始的子串，和s的当前位置开始的子串是否相同。如果循环结束，都没有找到不同的字符，那么此时看两个字符串的长度是否相差1，参见代码如下：

解法二：

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        for (int i = 0; i < min(s.size(), t.size()); ++i) {
            if (s[i] != t[i]) {
                if (s.size() == t.size()) return s.substr(i + 1) == t.substr(i + 1);
                if (s.size() < t.size()) return s.substr(i) == t.substr(i + 1);
                else return s.substr(i + 1) == t.substr(i);
            }
        }
        return abs((int)s.size() - (int)t.size()) == 1;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/161

类似题目：

Edit Distance

参考资料：

https://leetcode.com/problems/one-edit-distance/

https://leetcode.com/problems/one-edit-distance/discuss/50108/C%2B%2B-DP

https://leetcode.com/problems/one-edit-distance/discuss/50098/My-CLEAR-JAVA-solution-with-explanation

到此这篇关于C++实现LeetCode(161.一个编辑距离)的文章就介绍到这了,更多相关C++实现一个编辑距离内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(159.最多有两个不同字符的最长子串)

    [LeetCode] 159. Longest Substring with At Most Two Distinct Characters 最多有两个不同字符的最长子串 Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters. Example 1: Input: "eceba" Output: 3 Explanation: ti

  • C++实现LeetCode(154.寻找旋转有序数组的最小值之二)

    [LeetCode] 154. Find Minimum in Rotated Sorted Array II 寻找旋转有序数组的最小值之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]). Find the minimum element. Th

  • C++实现LeetCode(160.求两个链表的交点)

    [LeetCode] 160.Intersection of Two Linked Lists 求两个链表的交点 Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A:          a1 → a2 c1 → c2 → c3             B:     b1

  • C++实现LeetCode(157.用Read4来读取N个字符)

    [LeetCode] 157. Read N Characters Given Read4 用Read4来读取N个字符 Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters. Method read4: The API read4 reads 4 consecutive characters from t

  • C++实现LeetCode(155.最小栈)

    [LeetCode] 155. Min Stack 最小栈 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getM

  • C++实现LeetCode(156.二叉树的上下颠倒)

    [LeetCode] 156. Binary Tree Upside Down 二叉树的上下颠倒 Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the origina

  • C++实现LeetCode(158.用Read4来读取N个字符之二 - 多次调用)

    [LeetCode] 158. Read N Characters Given Read4 II - Call multiple times 用Read4来读取N个字符之二 - 多次调用 Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be ca

  • C++实现LeetCode(904.水果装入果篮)

    [LeetCode] 904. Fruit Into Baskets 水果装入果篮 In a row of trees, the `i`-th tree produces fruit with type `tree[i]`. You start at any tree of your choice, then repeatedly perform the following steps: Add one piece of fruit from this tree to your baskets.

  • C++实现LeetCode(161.一个编辑距离)

    [LeetCode] 161. One Edit Distance 一个编辑距离 Given two strings s and t, determine if they are both one edit distance apart. Note:  There are 3 possiblities to satisify one edit distance apart: Insert a character into s to get t Delete a character from s 

  • 最值得Java开发者收藏的网站

    Java是一种面向对象的编程语言,由Sun Microsystems公司在1995年的时候正式发布.直到今天,Java都一直是最受欢迎的编程语言之一.如今,Java应用于各种各样的技术领域,例如网站开发.Android开发.游戏开发.大数据等等. 在世界各地,成千上万的Java开发者进行着各式各样的软件开发项目.不同的开发者使用的工具不同,每一个项目所要求的技术也不同.但是,他们都会通过网络途径来为满足自己的学习需求或者为编程问题找到解决方法. 因此,我列举了11个能够帮助Java开发者提升编程

  • Windows配置VSCode+CMake+Ninja+Boost.Test的C++开发环境(教程详解)

    平时习惯了在Linux环境写C++,有时候切换到Windows想继续在同一个项目上工作,重新配置环境总是很麻烦.虽然Windows下用Visual Studio写C++只需要双击个图标,但我还是想折腾一下VS Code的环境配置.原因主要有两点:一是个人习惯上各种语言都在VS Code里面写,利用Git同步代码可以很方便地在不同平台开发同一个项目:二是有些情形下无法使用图形化界面,比如为Git配置CI(持续性集成)时显然不能用Visual Studio这个图形化的IDE来执行Windows环境的

  • golang如何去除多余空白字符(含制表符)

    golang如何去除多余空白字符(含制表符)

    看代码吧~ //利用正则表达式压缩字符串,去除空格或制表符 func compressStr(str string) string { if str == "" { return "" } //匹配一个或多个空白符的正则表达式 reg := regexp.MustCompile("\\s+") return reg.ReplaceAllString(str, "") } 补充:go语言去除字符串尾部所有空格 刷 leetcod

  • C++实现LeetCode(72.编辑距离)

    [LeetCode] 72. Edit Distance 编辑距离 Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a char

  • C++实现LeetCode(31.下一个排列)

    [LeetCode] 31. Next Permutation 下一个排列 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sor

  • C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)

    [LeetCode] 34. Find First and Last Position of Element in Sorted Array 在有序数组中查找元素的第一个和最后一个位置 Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity

  • C++实现LeetCode(74.搜索一个二维矩阵)

    C++实现LeetCode(74.搜索一个二维矩阵)

    [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • 推荐一个电信网络工程师讲解禁路由上网的破解方法

    ADSL共享上网有两种方式,一种是代理,一种是地址翻译(NAT),大家常说的路由方式其实就  是NAT方式,其实路由和NAT的原理还是有区别的,这里不作讨论,现在的ADSL猫一般都有NAT的  功能,用它本身的功能实现共享上网是比经济方便,本文主要讨论这种方式.转  要想阻断一台以上的计算机上网必须能发现共享后边的机器是否多于一台,NAT的工作原理如图  一所示,经过NAT转换后访问外网的内网的计算机的地址都变成了192.168.0.1而且MAC地址也转  换成了ADSL的MAC地址,也就是说,

随机推荐