elenashutova

 Profile Answers by elenashutova 

• Jul 20th, 2008

 

Let's think about the string as a vector with coordinates represented by each character ASCII value, i.e.
1st string (str1): (x1, x2, ..., xm)
where
x1 = str1[0], x2 = str1[1], ..., xm = str1[m-1]
2nd string (str2): (y1, y2, ..., yn)
y1 == str2[0], y2 == str2[1], ..., yn=str2[n-1]
Assume that m<n.
In this case the distance beween str1 and str2:
D(str1, str2) = [(x1-y1)^2 + (x2-y2)^2 + ... + (xm-ym)^2 + y(m+1)^2 + ....
+ y(n-1)^2 + yn^2]^(1/2)

rem132

 Profile Answers by rem132 

• Sep 2nd, 2008

 

Stanard approach is dynamic programming with complexity O(N*M).
Let strings are A[1..N] and B[1..M]. We use array DP[0..N][0..M]. DP[i][j] stores the answer for prefixes of length i and j. DP[N][M] is the answer.

DP[i][j] = i+j   (if i = 0 or j = 0)
DP[i][j] = (S1[i]==S2[j]) ? 1+DP[i-1][j-1] : 1+min(DP[i-1][j], DP[i][j-1])   (otherwise)

yzesong

 Profile Answers by yzesong 

• Aug 9th, 2009

 

The distance of two strings, like "car" and "cat", is 1. So all we need to do is, compare two strings one character by one character and get the distance value. The complexity is O(max(m,n)), m, n are the length of each string.

rrc_83

 Profile Answers by rrc_83 

• Jun 20th, 2010

 

In python -

# Input is string s1 and string s2

# Check which string is bigger (compares ascii value)
if s1 > s2:
  b, s = s1, s2
else :
  b, s  = s2, s1

# Covert string to list
l1, l2 = list(b) , list(s)

# Check lenght of string
if len(l1) < len(l2):
  looplength = len(l1)
else:
  looplength = len(l2)

# Run loop to min lenght - O(n)
for i in range(looplenght):
  distance = ord(l1[i]) - ord(l2[i])  # ord() converts char to Ascii value
  if distance != 0:
     # We have our distance from the first non-matching characters
     print "%s is the disatance"% distance
     break