1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//
//  main.cpp
//  回文字符串
//
//  Created by Jiao Liu on 8/9/17.
//  Copyright © 2017 ChangHong. All rights reserved.
//
#include <iostream>
#include <map>
using namespace std;
map<string, int> stack;
int bestChange(string str, long left, long right)
{
    if (stack.find(str.substr(left,right-left+1)) != stack.end()) {
        return stack[str.substr(left,right-left+1)];
    }
    if (left > right) {
        return 0;
    }
    int ret = 0;
    if (str[left] == str[right]) {
        ret = bestChange(str, left+1, right-1);
    }
    else
    {
        ret = min(bestChange(str, left+1, right)+1,bestChange(str, left, right-1)+1);
        ret = min(ret,bestChange(str, left+1, right-1)+1);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX