Author |
Topic: String Question (Read 1064 times) |
|
tuxilogy
Newbie
Posts: 45
|
 |
String Question
« on: Jul 1st, 2008, 8:28am » |
 Quote  Modify
|
Given a string A, and a string B, and a dictionary, how would you convert A to B in the minimum no of operations, given that:
i) All the intermediate words must be from the dictionary
ii) An ‘operation’ is defined as:
a) Delete any character from a string ex dog → do
b) Insert any character into a string ex cat → cart
c) Replace any character in the string with another ex cat → cot
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: String Question
« Reply #1 on: Jul 1st, 2008, 8:33am » |
Quote Modify
|
Use a maze solver on the implicit graph formed by the constraints of the problem (vertices are words in the dictionary, edges are valid operations that turn one word into another).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: String Question
« Reply #2 on: Jul 1st, 2008, 8:34am » |
Quote Modify
|
It boils down to finding the shortest path in a graph.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: String Question
« Reply #3 on: Jul 1st, 2008, 8:35am » |
Quote Modify
|
Well, as towr suggests... 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print