Google+ Followers

Monday, August 7, 2017

[Leetcode] One Edit Distance, Solution

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

[Thoughts]
这是个简化版。只要考虑几种可能, 如果s.length == t.length,只要看看不相同的字符是否超过一个即可。如果s.length < t.length,看看在s中插入一个字符是否能解决问题。

[Code]
1:    bool isOneEditDistance(string s, string t) {  
2:      int lena = s.size();  
3:      int lenb = t.size();  
4:      if(lenb > lena) return isOneEditDistance(t, s);  
5:      if(lena - lenb > 1) return false;  
6:        
7:      int diff = 0;  
8:      for(int i =0, j = 0; i< s.size() && j< t.size() && diff < 2; i++, j++) {  
9:        if(s[i] != t[j]) {  
10:          diff++;  
11:          if(lena != lenb) t.insert(j, 1, s[i]);  
12:        }  
13:      }  
14:        
15:      if((lena != lenb) && diff <2) return true;  
16:      if((lena == lenb) && diff ==1) return true;  
17:      return false;  
18:    }  

Post a Comment