2015年10月24日星期六

Leetcode 161 One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.
Solution 1:  Move p1,p2 from start and q1,q2 from end. if related character is same between s and t. keep moving forward p1/p2 and moving back q1/q2. Details as below:
 public class Solution {  
   public boolean isOneEditDistance(String s, String t) {  
     int m=s.length(), n=t.length();  
     if (Math.abs(m-n)>1) return false;  
     int p1=0, p2=0;  
     while (p1<m && p2<n && s.charAt(p1)==t.charAt(p2)) {  
       p1++;   
       p2++;  
     }  
     p1--;   
     p2--;  
     int q1=m-1, q2=n-1;  
     while (q1>=0 && q2>=0 && s.charAt(q1)==t.charAt(q2)) {  
       q1--;   
       q2--;  
     }  
     q1++;   
     q2++;  
     if (q1-p1==2 && q2-p2==2) return true;  
     if (q1-p1==1 && q2-p2==2) return true;  
     if (q1-p1==2 && q2-p2==1) return true;  
     return false;  
   }  
 }  

没有评论:

发表评论