字符串转换 [英] String transformation

问题描述

我碰到下面的<一个href="http://www.glassdoor.com/Interview/Given-two-words-CAT-FAR-determine-if-you-can-get-from-the-first-to-the-second-via-single-transformations-of-valid-word-QTN_172828.htm"相对=nofollow>文章，这让我感兴趣，这方面的问题。

I came across the following article which got me interested in this particular problem.

由于两个词CAT，远确定是否可以从第一个获得   通过单一的变换有效的话....例如第二1   改造可以让你从猫CAR改变T可R，然后又   让你的车到FAR改变C至F ......都是有效的英语   话。

Given two words "CAT", "FAR" determine if you can get from the first to the second via single transformations of valid words....e.g. 1 transformation gets you from CAT to CAR changing T to R, then another gets you from CAR to FAR changing the C to F...all are valid english words.

任何想法？真的不知道如何开始是诚实的。如果你在正确的方向指向我，那就够了。谢谢！

Any ideas? Not really sure how to begin to be honest. If you point me in the right direction, then that will be enough. Thanks!

推荐答案

作为<一说href="http://stackoverflow.com/questions/1521958/shortest-path-to-transform-one-word-into-another/1521973#1521973">this回答（感谢，AIX），这是一个最短路径问题，可以有效地解决与的 A *算法使用汉明距离（即通过信件数量这两个词的不同）作为一种启发式的。

As noted in this answer (thanks, aix), this is a shortest-path problem, and can be efficiently solved with the A* algorithm using the Hamming distance (i.e. the number of letters by which two words differ) as a heuristic.

这篇关于字符串转换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！