Warning! You are probably being recorded (and transcribed).
Approximate overview
When will the regrades get done?
This coming weekend. (Maybe sooner.)
Given two strings, \(S\) and \(T\), what is the fewest number of changes needed to convert \(S\) to \(T\)?
Valid changes:
delete(i) - delete the letter at position i in S.insert(i,ch) - insert the letter ch immediately before position i.replace(i,ch) - replace the letter at position i with ch.
(This is often called substitute.)ed(S, T)
// Base case(s)
if (S == T)
return 0
else if (S.length == 0)
return T.length // Insert a bunch of characters
else if (T.length == 0)
return S.length // Delete a bunch of characters
// Easy case
else if S[0] == T[0]
return ed(S.substring(1), T.substring(1))
// Minimize
else
return min(// Delete 1st character of S
1 + ed(S.substring(1), T),
// insert 1st character of T at start of S
1 + ed(S, T.substring(1)),
// replace 1st character of S with 1st of T
1 + ed(S.substring(1), T.substring(1)))
ed(S[0:row],T[0:col]).row elements of Scol elements of T. TARGET
s p a m
0 1 2 3 4
+---+---+---+---+---+
0 | | | | | |
S +---+---+---+---+---+
O s 1 | | | | | |
U +---+---+---+---+---+
R a 2 | | | | | |
C +---+---+---+---+---+
E m 3 | | | | | |
+---+---+---+---+---+
r 4 | | | | | |
+---+---+---+---+---+
Note that we’ve flipped almost everything from our LCS solution.
ed(S,T)
edTable = fillTableED(S,T)
return edTable[S.length, T.length]
fillTableED(S,T)
// Initialize row 0
for (int col = 0; col <= T.length; col++)
table[0, col] = col
// Initialize column 0
for (int row = 0; row <= S.length; row++)
table[row, 0] = row
// Loop
for (row = 1; row <= S.length; row++)
for (col = 1; col <= T.length; col++)
if (S[row] == T[col])
table[row,col] = table[row-1, col-1]
else
min(1 + table[row-1, col-1], // Replace
1 + table[row, col-1], // Insert
1 + table[row-1, col]) // Delete
TARGET
s p a m
0 1 2 3 4
+---+---+---+---+---+
0 | 0 | 1 | 2 | 3 | 4 |
S +---+---+---+---+---+
O s 1 | 1 | 0 | 1 | 2 | 3 |
U +---+---+---+---+---+
R a 2 | 2 | 1 | 1 | 1 | 2 |
C +---+---+---+---+---+
E m 3 | 3 | 2 | 2 | 1 | 1 |
+---+---+---+---+---+
r 4 | 4 | 3 | 3 | 2 | 2 |
+---+---+---+---+---+
\(O((|S|+1)\times(|T|+1))\) because that’s the size of the table and each cell is constant amount of work to fill.
\[O(|S| + |T| + |S|\times|T|)\]edits(S,T)
edTable = fillTableED(S,T)
return editsHelper(S, T, edTable, S.length, T.length, {})
editsHelper(S, T, edTable, col, row, edits)
// If we reach the top left of the table, no edits are needed
if (col == 0) && (row == 0)
return edits
// If the target is empty, we need to delete everything
else if (col == 0)
// Think carefully about this for Project 5
for (r = row-1; r >= 0; r--)
edits.append(Delete(r))
return edits
// If the source is empty, we need to ?
else if (row == 0)
for (c = col-1; c >= 0; c--)
edits.append(Insert(0,T[c]))
return edits
// If the current characters match, we don't need an edit here
else if S[row] == T[col]
return editsHelper(S, T, edTable, col-1, row-1, edits)
// At this point, we need an edit
else
// Compute the best direction
best = min(edTable[row-1, col-1], // Represents Replace
edTable[row-1, col], // Represents Delete
edTable[row, col-1]) // Represents Insert
if (edTable[row-1, col-1] == best)
edits.append(Replace(row-1, T[col-1])
return editsHelper(S, T, edTable, row-1, col-1, edits)
else if (edTable[row-1, col] == best)
edits.append(Delete(row-1))
return editsHelper(S, T, edTable, row-1, col, edits)
else
edits.append(Insert(row, T[col-1])) // Need to check!
return editsHelper(S, T, edTable, row, col-1, edits)
We can also make this iterative.
edits(S,T)
edTable = fillTableED(S,T)
edits = {}
col = T.length
row = S.length
while (col >= 0) && (row >= 0)
if (row =- 0)
edits.append(Insert(0, T[col-1]))
col = col - 1
else if col == 0
edits.append(Delete(row-1))
row = row - 1
else if S[row] == T[col]
row = row - 1
col = col - 1
else
// Compute the best direction
best = min(edTable[row-1, col-1], // Represents Replace
edTable[row-1, col], // Represents Delete
edTable[row, col-1]) // Represents Insert
if (edTable[row-1, col-1] == best)
edits.append(Replace(row-1, T[col-1])
row = row - 1
col = col - 1
else if (edTable[row-1, col] == best)
edits.append(Delete(row-1))
row = row - 1
else
edits.append(Insert(row, T[col-1])) // Need to check! (looked right)
col = col - 1
return edits
Example ——-
// samr
Delete(3) // sam
Insert(1,'p') // spam
String alignment! Given two strings \(S\) and \(T\). You can insert spaces anywhere you want in \(S\) and \(T\). Goal: Minimize the mismatches after inserting spaces.
S = actactact
T = tagtgcat
****** *
S = actactac_t
T = __tagtgcat
** * * *
Where do we put the spaces to minimize the total number of mismatches?