Sunday, January 11, 2015

LeetCode 161: One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.
public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        // The following two cases satisfy the requirements:
        // 1. If the lengths of both strings are identical, just modify one character can make them equal;
        // 2. If the their lengths only one difference, just delete one character can make them equal.
        int m = s.length();
    	int n = t.length();
    	    
    	if (Math.abs(m-n) > 1)
    	    return false;
    	
    	int i, j;    
    	int dist = 0;
    	
    	for (i=0, j=0; i<m && j<n; i++, j++)
    	{
    	    if (s.charAt(i) != t.charAt(j))
    	    {
    	        if (m < n)
    	            i--;
    	        else if (m > n)
    	            j--;
    	        
    	        dist++;
    	    }
    	}
    	
    	while (i++ < m)
    	    dist++;
    	    
    	while (j++ < n)
    	    dist++;
    	    
    	return dist == 1;
    }
}

No comments:

Post a Comment