美文网首页
字符串的动态规划问题(Java)

字符串的动态规划问题(Java)

作者: dreamsfuture | 来源:发表于2018-03-18 17:26 被阅读0次

动态规划问题基本就是用空间换时间

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算法的应用之单词转换(词梯问题)

本文是对以上三篇文献的总结,细节方面请重点参考这三篇文章。

[4] Java动态规划 实现最长公共子序列以及最长公共子字符串

相关文章

网友评论

      本文标题:字符串的动态规划问题(Java)

      本文链接:https://www.haomeiwen.com/subject/nrgeqftx.html