前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >String - 161. One Edit Distance

String - 161. One Edit Distance

作者头像
ppxai
发布2020-09-23 17:13:15
3400
发布2020-09-23 17:13:15
举报
文章被收录于专栏:皮皮星球皮皮星球
  1. One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

Have you met this question in a real interview?  Yes

Problem Correction

Example

Example 1:

代码语言:javascript
复制
Input: s = "aDb", t = "adb" 
Output: true 

Example 2:

代码语言:javascript
复制
Input: s = "ab", t = "ab" 
Output: false
Explanation:
s=t ,so they aren't one edit distance apart

思路:

题目意思是两个字符串,通过一次替换或者增加或者删除操作,使得两个字符串相等。增加和删除其实属于一类,因为相对于短的字符串是增加,而长的字符串是减少,所以问题分类为两类。一类是替换,一类是增加删除。替换的在一次遍历的时候,只允许相同位置,出现一次字符不相同,增加和删除也是类似,找出相邻字符不同的情况只允许出现一次。

代码:

java:

代码语言:javascript
复制
 public class Solution {
    /**
     * @param s: a string
     * @param t: a string
     * @return: true if they are both one edit distance apart or false
     */
    public boolean isOneEditDistance(String s, String t) {
        // write your code here
        if (s == null && t == null) return true;
        
        if (s == null || t == null) return false;
        
        int slen = s.length();
        int tlen = t.length();
        
        if (slen == tlen) return isOneChangeDistance(s, t);
        else if (slen - tlen == 1) return isOneRemoveDistance(s, t);
        else if (tlen - slen == 1) return isOneRemoveDistance(t, s);
        
        return false;
    }
    
    private boolean isOneChangeDistance(String s, String t) {
        int len = s.length();
        boolean flag = false;
        for (int i = 0; i < len; i++){
            if (s.charAt(i) != t.charAt(i)) {
                if (flag) {
                    return false;
                } else {
                    flag = true;
                }
            }
        }
        
        return flag;
    }
    
    private boolean isOneRemoveDistance(String s, String t) {
        int len = t.length();
        boolean flag = false;
        
        for (int slow = 0, fast = 0; slow < len; slow++) {
            if (s.charAt(fast) != t.charAt(slow)) {
                if (flag) {
                    return false;
                } 
                flag = true;
                slow--;
            }
            fast++;
        }
        
        return true;
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年07月02日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Example
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档