找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 15270|回复: 13
收起左侧

[米群网刷题小分队] 我也发一个 [Leetcode] One Edit Distance

  [复制链接]
发表于 12-7-2014 09:24 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
题目:Given two strings S and T, determine if they are both one edit distance apart.https://oj.leetcode.com/problems/one-edit-distance/

其实就是考虑s和t逐个比较……虽然名义上分两种情况,但是一个循环能搞定……之前好像看到过一个人大概也这么写的吧,但是好像找不到了,所以我自己写了下,崇尚短码。。。
时间复杂度 O(max(lens,lent))  
空间复杂度 O(1)
陷阱 注意s是t的前缀的情况,例如"abc"和“abcd"这样的。

  1. class Solution {
  2. public:
  3.     bool isOneEditDistance(string s, string t) {
  4.         if (s.length() > t.length()) {
  5.             swap(s,t);
  6.         }
  7.         if (t.length() - s.length() > 1) {
  8.             return false;
  9.         }
  10.         bool have = false;
  11.         for (int i = 0, j = 0; i < s.length(); ++i,++j) {
  12.             if (s【i】 != t[j]) {
  13.                 if (have) {
  14.                     return false;
  15.                 }
  16.                 have = true;
  17.                 if (s.length() < t.length()) {
  18.                     --i;
  19.                 }
  20.                
  21.             }
  22.         }
  23.         return (have) || (s.length() < t.length());
  24.     }
  25. };
复制代码



本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

91

主题

47

精华

1916

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1916

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-15-2014 12:21 AM | 显示全部楼层
本帖最后由 MengMa 于 12-15-2014 12:25 AM 编辑

跟随版主大人的思路,贴一个我翻译的java解法。
p.s. java里没法通过交换来改变字符串的值。

//has的意思是,已经有一个字符不同了。
  1. public class Solution {
  2.     public boolean isOneEditDistance(String s, String t)
  3.     {
  4.         if(Math.abs(t.length() - s.length()) > 1) return false;
  5.         if(s.length() > t.length()) return helper(t,s);
  6.         return helper(s, t);
  7.     }
  8.     private boolean helper(String s, String t)
  9.     {
  10.         boolean has = false;
  11.         for(int i = 0, j = 0; i < s.length(); ++i, ++j)
  12.         {
  13.             if(s.charAt(i) != t.charAt(j))
  14.             {
  15.                 if(has) return false;
  16.                 has = true;
  17.                 if(s.length() < t.length()) --i;
  18.             }
  19.         }
  20.         return has || s.length() < t.length();
  21.     }
  22. }
复制代码
回复 支持 1 反对 0

使用道具 举报

18

主题

6

精华

257

积分

高级会员

Rank: 3Rank: 3

积分
257
发表于 12-7-2014 11:24 AM | 显示全部楼层
这个看不到题啊,edit distance 为1也是返回false吗?
这个逻辑太赞了,省了好多代码,贴一个c++的版本
  1. class Solution {
  2. public:
  3.     bool isOneEditDistance(const string &s, const string &t) {
  4.         if (s.size() > t.size()) return isOneEditDistance(t, s);
  5.         if (t.size() - s.size() > 1) return false;
  6.         bool misMatch = false;
  7.         for (int i = 0, j = 0; i < s.size(); ++i, ++j) {
  8.             if (s【i】 != t[j]) {
  9.                 if (misMatch) return false;
  10.                 misMatch = true;
  11.                 if (t.size() > s.size()) {
  12.                     i--;
  13.                 }
  14.             }
  15.         }
  16.         return misMatch || t.size() > s.size();
  17.     }
  18. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| 发表于 12-7-2014 11:30 AM | 显示全部楼层
freshwind 发表于 12-7-2014 11:24 AM
这个看不到题啊,edit distance 为1也是返回false吗?
这个逻辑太赞了,省了好多代码,贴一个c++的版本

要恰好为1.。。我的就是C++啊
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表