2707.字符串中的额外字符

首先是用C语言写，因为平时我开发需要熟悉C。其次会详细解释一下这道题算法的知识点，但是是动态规划。这道题还有另一种更低时间复杂度的，这里不讲。

1. 这道题是线性的动态规划。《图解算法》里二维的动态规划讲的很好，可惜没讲线性的。
2. 这题的母题应该是最大连续子序列和、最长不下降子序列。他们的共同点是状态的后无效性：当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策在已有的一个或者若干个状态的基础上进行。类比母题，也就是说这里对左端点的枚举是没有必要的。总的字符串长n，当前子问题字符串长i，比上一次增加了1个字符，我只用确定这个字符对以前状态的影响就好了。
   
   如上图，我们保存了字符串从长度为1开始的一系列信息，罗列每次多增加一个字符，会对已有信息的影响，然后更新状态量。

int minExtraChar(char * s, char ** dictionary, int dictionarySize) {
	int length = strlen(s)+1; // 要匹配的字符串长度，不会包含'\0'的, +1是因为初始状态要写0
	int dp[length]; // 保存子问题的状态信息
	int i;
	//把字典放入哈希表用于查找
	for (i = 0; i < dictionarySize; i++){
		add(dictionary[i]);
	}
	dp[0] = 0; // 初始化字符串长度为0
	for (int i = 1; i < length; i++) {  // 枚举子问题
		//如果整个状态没有变化
		dp[i] = dp[i - 1] + 1; 
		//罗列可能造成状态变化的原因，即与字典中的每个字符串做后缀匹配
		for (int j = i - 1; j >= 0; j--) { 
			if (find(substr(s, j, i-j))!=NULL) {
				dp[i] = min(dp[i], dp[j]); 
			}
		}
	}
	hashFree();
	return dp[length-1];
}

C的哈希表在#include “uthash.h”，但是OJ要自己写。

typedef struct {
    char* key;
    UT_hash_handle hh;
} Hash;

Hash *myHash = NULL;

int min(int a, int b) {
	return a > b ? b : a;
}

char *substr(char *str, int start, int len) {
	char *sub = (char*) malloc(len + 1);
	strncpy(sub, str + start, len);
	sub[len] = '\0';
	return sub;
}

Hash* find(char* key)
{
    Hash *s = NULL;
    HASH_FIND_STR(myHash, key, s);
    return s;
}

void add(char* key){
    Hash *s = find(key);
    if(s == NULL){
    	s = (Hash *)malloc(sizeof(Hash));
    	s->key = key;
    	HASH_ADD_STR(myHash, key, s);
    }
}

void hashFree() {
	Hash *curr = NULL, *tmp = NULL;
	HASH_ITER(hh, myHash, curr, tmp) {
		HASH_DEL(myHash, curr);
		free(curr);
	}
}