相似单词变换

#include <string>
#include<algorithm>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	string str1, str2;
	while (cin >> str1 >> str2){
		int len1 = str1.size();
		int len2 = str2.size();
		vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1,0));
		for (int i = 0; i <= len1; i++){
			dp[i][0] = i;
		}
		for (int j = 0; j <= len2; j++){
			dp[0][j] = j;
		}
		for (int i = 1; i <= len1; i++){
			for (int j = 1; j <= len2; j++){
				if (str1[i - 1] == str2[j - 1])
					dp[i][j] = dp[i - 1][j - 1];
				else
					dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
			}
		}
		cout << dp[len1][len2] << endl;
	}
	return 0;
}

# coding:utf8
def count_opera():
	hey = raw_input()
	while (not hey or len(hey.split(' '))!=2):
		print "Input Correct String"
		hey = raw_input()
	need_change, porpose = hey.split(' ')
	need_change_length = len(need_change)
	porpose_length = len(porpose)
	if need_change_length == porpose_length:
		print same_length(need_change, porpose)
	if need_change_length < porpose_length:
		print need_insert(need_change, porpose)
	if need_change_length > porpose_length:
		print need_delete(need_change, porpose)
	
def same_length(string_A, string_B):
	count = 0
	for index in xrange(len(string_B)):
		if string_A[index] != string_B[index]:
			count += 1
	return count

def need_insert(string_A, string_B):
	count = 0
	a_list = list(string_A)
	for index in xrange(len(string_B)):
		if a_list[index] != string_B[index]:
			a_list.insert(index, string_B[index])
			count += 1
		if len(a_list) == len(string_B):
			string_A = ''.join(a_list)
			break
	change_cnt = same_length(string_A, string_B)
	count += change_cnt
	return count
			
def need_delete(string_A, string_B):
	count = 0
	a_list = list(string_A)
	while (len(a_list) != len(string_B)):
		a_list = delete_and_judge(a_list, string_B)
		count += 1
	string_A = ''.join(a_list)
	change_cnt = same_length(string_A, string_B)
	count += change_cnt
	return count

def delete_and_judge(a_list, string_B):
	length = len(a_list)
	for index in xrange(length):
		if a_list[index] != string_B[index]:
			del a_list[index]
			return a_list

if __name__ == "__main__":
	count_opera()

#include<iostram>
#include<vector>
#include<string>
using namespace std;

int getsize(const string& str1,const string& str2,int pos1,int pos2,vector<vector<int>>& mark;)
{
 int result=10000;
    int size1=str1.size();
    int size2=str2.size();
 if(mark[pos1][pos2]!=-1)
 {
  return mark[pos1][pos2];
 }
 if(pos1==size1||pos2==size2)
 {
  if(pos1==0)
   return size2-pos2;
  else
   return size1-pos1;
 }
 
    if(str1[pos1]==str[pos2])
    {
  int tmp=getsize(str1,str2,pos1+1,pos2+1);
  if(result>tmp)
   result=tmp;
 }
 else
 {
 // if(size1-pos1>=size2-pos2)
  //{
   int tmp=1+ getsize(str1,str2,pos1+1,pos2);
   if(result>tmp)
    result=tmp;
 // }
  //if(size1-pos1<=size2-pos2)
  //{
   tmp=1+ getsize(str1,str2,pos1,pos2+1);
   if(result>tmp)
    result=tmp;
  //}
 }
 mark[pos1][pos2]=result;
 return result;
}

int main()
{
 string str1,str2;
 cin>>str1>>str2;
 //int mark[str1.size()+1][str2.size()+1]={0};
 vector<vector<int>> mark(str1.size()+1,vector<int>(str2.size(),-1)+1);
 int result=getsize(str1,str2);
 cout<<result<<endl;
 return 1;
}