最少操作次数使两个字符串相等

给定两个字符串，仅由小写字母组成，它们包含了相同字符。 求把第一个字符串变成第二个字符串的最小操作次数，且每次操作只能对第一个字符串中的某个字符移动到此字符串中的开头。 例如给定两个字符串“abcd" "bcad" ，输出：2，因为需要操作2次才能把"abcd"变成“bcad" ，方法是：abcd->cabd->bcad。

下面的代码是实现两个字符串相等的操作，还没有验证是最少操作次数。

def getBeforeOrlast(stra,c):
	at=getcharIndex(stra,c)
	r=(at-1) % len(stra)
	return stra[r]
def getcharIndex(str1,char):
	for i in range(len(str1)):
		if char==str1[i]:
			return i
	return None
def changeB(strb,char):#move the find char to head
	at=getcharIndex(strb,char)
	strb=strb[:at]+strb[at+1:]
	return char+strb
s1="acbd"
s2=‘abcd‘
while s1<>s2:
	char=getBeforeOrlast(s1,s2[0])#find the char in destination string that is before first char in source string
	s2=changeB(s2,char)
	print s1,s2
	raw_input()

最少操作次数使两个字符串相等

原文：http://blog.csdn.net/mahongquan/article/details/19812961