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:    }  

5 comments:

Unknown said...

Hello Blog admin I want to share some useful articles here for anyone looking for financial help to get through.
I want to talk about a God Fearing loan lender who lend me $400,000.00 to finance my business when I couldn't get help from my community bank here in Ohio, Mr Pedro was very nice to work with in every aspect of financial assistance so I will advise anyone here looking for a loan to contact Mr Pedro on Email / WhatsApp text.
Pedro Email: pedroloanss@gmail.com
Mr Pedro WhatsApp text: +1 863 231 0632

Josephy said...

Leetcode.com is a website where people can post and share computer programming problems. Users can also create problems and make them available for other people to solve. multi platform streaming

Josephy said...

I'm so amazed together with you that will make your blog like this to be really great so we truly wanted to have a nice and interesting blogs such as this. best chocolate in riyadh

Josephy said...

I like your blog post. Keep on writing this type of great stuff. I'll make sure to follow up on your blog in the future. woon clothing

Josephy said...

Nice post having excellent contents.This is exactly what I've been looking for.Thank you very good. I simply want to tell you that I am new to weblog and definitely liked this blog site. Very likely I’m going to bookmark your blog . home renovation services dubai