动态规划问题基本就是用空间换时间
1.最长公共子串[1]
①定义
最长公共子串（Longest Common Substring）是指两个字符串中的最长的公共子串，要求子串一定是连续。
②分析
一个字符串是另外一个字符串的子串，而且是连续的，如果利用矩阵表示"bab"和"caba"这两个字符串，如下图所示：
图1 字符串矩阵
斜对角为1的表示对应的最长连续子串，也即“ab”
二维矩阵比较耗费空间，所以如果如下图2所示，把下一个匹配的内容加上前一个，然后需要结果的时候找数组最大的值便可以：
图2 一维数组实现最长连续子串
③公式
二维矩阵：dp[i][j]=dp[i-1][j-1]+1
一维数组：new_dp[i] = 第i条对角线的长度
④代码实现
public class LongestCommonSubstring{
public static int compute(char[] str1, char[] str2){
int size1 = str1.length;
int size2 = str2.length;
if (size1 == 0 || size2 == 0) return 0;
// 原始字符串中最长子串的起始位置
int start1 = -1;
int start2 = -1;
int longest = 0;
//拿字符串1做基准，检索最长连续子串
for (int i = 0; i < size1; ++i){
int m = i;
int n = 0;
int length = 0;
while (m < size1 && n < size2){
if (str1[m] != str2[n]){ //遇到不相等，则需要重新开始
length = 0;
}
else{
++length;
if (longest < length){
longest = length;
start1 = m - longest + 1; //记录下最长公共子串的起始位置
start2 = n - longest + 1;
}
}
++m;
++n;
}
}
// 拿字符串2做基准，进行再次搜索
for (int j = 1; j < size2; ++j){
int m = 0;
int n = j;
int length = 0;
while (m < size1 && n < size2){
if (str1[m] != str2[n]){
length = 0;
}
else {
++length;
if (longest < length){
longest = length;
start1 = m - longest + 1;
start2 = n - longest + 1;
}
}
++m;
++n;
}
}
System.out.printf("from %d of str1 and %d of str2\n", start1, start2);
return longest;
}
public static void main(String[] args) {
String a = "Tom Hanks";
String b = "Hankcs";
System.out.println(LongestCommonSubsequence.compute(a.toCharArray(), b.toCharArray()));
}
}
2.最长公共子序列
①定义
最长公共子序列（Longest Common Subsequence）是指两个字符串中的最长公共子序列，不要求子序列连续。
②分析
略
③公式
0 (如果i=0且j=0)
dp[i][j] = dp[i-1][j-1] + 1 （如果i和j>0，且A[i]=B[j]）
max(dp[i][j-1], dp[i-1][j]) （如果i和j>0，且A[i]!=B[j]）
④代码实现
public class LongestCommonSubsequence{
public static int compute(char[] str1, char[] str2){
int substringLength1 = str1.length;
int substringLength2 = str2.length;
// 构造二维数组记录子问题A[i]和B[j]的LCS的长度
int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];
// 从后向前，动态规划计算所有子问题。也可从前到后。
for (int i = substringLength1 - 1; i >= 0; i--){
for (int j = substringLength2 - 1; j >= 0; j--){
if (str1[i] == str2[j])
opt[i][j] = opt[i + 1][j + 1] + 1;// 状态转移方程
else
//索引加的不同，表示参考基准不同
opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);// 状态转移方程
}
}
System.out.println("substring1:" + new String(str1));
System.out.println("substring2:" + new String(str2));
System.out.print("LCS:");
int i = 0, j = 0;
while (i < substringLength1 && j < substringLength2){
if (str1[i] == str2[j]){
System.out.print(str1[i]); //逐个输出最长公共子串
i++; j++;
}
else if (opt[i + 1][j] >= opt[i][j + 1]) i++;
else j++;
}
System.out.println();
return opt[0][0]; //最长公共子串的长度
}
public static void main(String[] args) {
String a = "hello, word";
String b = "hi, how are you";
System.out.println(LongestCommonSubsequence.compute(a.toCharArray(), b.toCharArray()));
}
}
3.相似单词变换[2]
①题目描述
英文单词有很多非常相似，比如：see和seek、cat和cut等，现在提供3种编辑操作：insert、remove、replace，通过在单词1上进行这些操作，可以让单词1变成单词2
那么问题来了，如何只用最小次数的编辑操作，可以让字符串1变成字符串2？
②说明
1）3种编辑操作的代价是一样的
2）并且每次只能操作一个字符串的一个字母
3）只需要考虑在字符串1上进行编辑操作即可
③输入
输入一行，有两个字符串，以空格分隔。
④输出
输出为最小编辑次数。
⑤样例输入
geek gesek
⑥样例输出
1
⑦分析
⑧公式
dp[ii-1][j-1] (如果i和j>0，且A[i]=B[j])
dp[i][j] = min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} (如果i和j>0，且A[i]!=B[j])
⑨代码实现
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String str1 = in.next();
char[] array1 = str1.toCharArray();
String str2 = in.next();
char[] array2 = str2.toCharArray();
int n = array1.length;
int m = array2.length;
int[][] temp = new int[n][m];
for (int i = 0; i < n; i++) {
temp[i][0] = i;
}
for (int i = 0; i < m; i++) {
temp[0][i] = i;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (array1[i] == array2[j]) {
temp[i][j] = temp[i - 1][j - 1];
} else {
temp[i][j] = minThree(temp[i - 1][j] + 1, temp[i][j - 1] + 1, temp[i - 1][j - 1] + 1);
}
}
}
System.out.println(temp[n - 1][m - 1]);
}
}
public static int minTwo(int a, int b) {
return a > b ? b : a;
}
public static int minThree(int a, int b, int c) {
int d = minTwo(a, b);
int min = minTwo(d, c);
return min;
}
}
4.最短路径算法-Dijkstra算法的应用之单词转换(词梯问题)[3]
问题描述
在英文单词表中，有一些单词非常相似，它们可以通过只变换一个字符而得到另一个单词。比如：hive-->five；wine-->line；line-->nine；nine-->mine.....
那么，就存在这样一个问题：给定一个单词作为起始单词(相当于图的源点)，给定另一个单词作为终点，求从起点单词经过的最少变换(每次变换只会变换一个字符)，变成终点单词。
要求
给定两个单词，一个作为源点，另一个作为终点，需要找出从源点开始，经过最少次单个字母替换，变成终点单词，这条变换路径中经过了哪些单词？
Dijkstra算法利用的是BFS原理实现的
Dijkstras_progress_animation
算法分析
①从文件中读取单词：把单词数据读取到一个List<String>中，然后利用List<String>构造一个图数据结构
②图数据结构利用邻接表实现：把图中的每一个顶点放入到map中，实现顶点与其邻接点的对应，Map<String, List<String>> adjWords = new TreeMap<>();
③图数据结构实现的方式：逐个读取List<String>中的单词，判断后面的单词是否与本单词只相差一个字母，若是则本单词作为map中的String key，对应的邻接表为List<String> value，并向value中增加数据
④Dijkstra算法分析：求解无向图 从String start 到 String end 的最短路径.无向图的Dijkstra实现只需要一个队列，采用“广度”遍历的思想从源点开始向外扩散求解图中其他顶点到源点的距离。
代码实现
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.TreeMap;
public class WordLadder {
/*
* 从文件中将单词读入到List<String>. 假设一行一个单词,单词没有重复
*/
public static List<String> read(final String filepath) {
List<String> wordList = new ArrayList<String>();
File file = new File(filepath);
FileReader fr = null;
BufferedReader br = null;
String lines = null;
String word = null;
try {
fr = new FileReader(file);
br = new BufferedReader(fr);
String line = null;
int index = -1;
while ((lines = br.readLine()) != null) {
// word = line.substring(0, line.indexOf(" ")).trim();
line = lines.trim();
index = line.indexOf(" ");
if (index == -1)
continue;
word = line.substring(0, line.indexOf(" "));
wordList.add(word);
}
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
fr.close();
br.close();
} catch (IOException e) {
}
}
return wordList;
}
/**
* 根据单词构造邻接表
* @param theWords 包含所有单词List
* @return Map<String, List<string>>key:表示某个单词, Value:与该单词只差一个字符的单词
*/
public static Map<String, List<String>> computeAdjacentWords(
List<String> theWords) {
Map<String, List<String>> adjWords = new TreeMap<>(); //单词的图结构：邻接表实现
Map<Integer, List<String>> wordsByLength = new TreeMap<>();
for (String word : theWords)
update(wordsByLength, word.length(), word);
for (List<String> groupWords : wordsByLength.values()) {
String[] words = new String[groupWords.size()];
groupWords.toArray(words);
//创建单词的图数据结构
for (int i = 0; i < words.length; i++)
for (int j = i + 1; j < words.length; j++)
if (oneCharOff(words[i], words[j])) {
update(adjWords, words[i], words[j]);
update(adjWords, words[j], words[i]);
}
}
return adjWords;
}
public static Map<String, List<String>> computeAdjacentWords2(List<String> theWords){
Map<String, List<String>> adjWords = new TreeMap<>();
String[] words = new String[theWords.size()];
words = theWords.toArray(words);
for(int i = 0; i < words.length; i++)
for(int j = i+1; j < words.length; j++)
if(oneCharOff(words[i], words[j])){
update(adjWords, words[i], words[j]);//无向图,i--j
update(adjWords, words[j], words[i]);//j--i
}
return adjWords;
}
//判断两个单词是否只有一个不同：只替换一个字符变成另一单词
private static boolean oneCharOff(String word1, String word2) {
if (word1.length() != word2.length())//单词长度不相等,肯定不符合条件.
return false;
int diffs = 0;
for (int i = 0; i < word1.length(); i++)
if (word1.charAt(i) != word2.charAt(i))
if (++diffs > 1)
return false;
return diffs == 1;
}
//将单词添加到邻接表中
private static <T> void update(Map<T, List<String>> m, T key, String value) {
List<String> lst = m.get(key);
if (lst == null) {//该 Key是第一次出现
lst = new ArrayList<String>();
m.put(key, lst);
}
lst.add(value);
}
/**
* 使用Dijkstra算法求解从 start 到 end 的最短路径
* @param adjcentWords 保存单词Map,Map<String, List<string>>key:表示某个单词, Value:与该单词只差一个字符的单词
* @param start 起始单词
* @param end 结束单词
* @return 从start 转换成 end 经过的中间单词
*/
public static List<String> findChain(Map<String, List<String>> adjcentWords, String start, String end){
Map<String, String> previousWord = new HashMap<String, String>();//Key:某个单词,Value:该单词的前驱单词
Queue<String> queue = new LinkedList<>();
queue.offer(start);
while(!queue.isEmpty()){
String preWord = queue.poll();
List<String> adj = adjcentWords.get(preWord);
for (String word : adj) {
//代表这个word的'距离'(前驱单词)没有被更新过.(第一次遍历到该word),每个word的'距离'只会被更新一次.
if(previousWord.get(word) == null){//理解为什么需要if判断
previousWord.put(word, preWord);
queue.offer(word);
}
}
}
previousWord.put(start, null);//记得把源点的前驱顶点添加进去
return geChainFromPreviousMap(previousWord, start, end);
}
private static List<String> geChainFromPreviousMap(Map<String, String> previousWord, String start, String end){
LinkedList<String> result = null;
if(previousWord.get(end) != null){
result = new LinkedList<>();
for(String pre = end; pre != null; pre = previousWord.get(pre))
result.addFirst(pre);
}
return result;
}
}
参考文献
[1] 最长公共子串、最长公共子序列的Java实现与NLP应用
[2] 2017年爱奇艺校招Java研发笔试编程题（2个）
[3] 最短路径算法-Dijkstra算法的应用之单词转换(词梯问题)
本文是对以上三篇文献的总结，细节方面请重点参考这三篇文章。
