首页 > 代码库 > 【数据结构与算法】LCS(不连续)
【数据结构与算法】LCS(不连续)
这个问题很经典,典型的动态规划,动态规划就是填一个表,然后遍历一下就行了。
- 代码实现
/** * 源码名称:LCSequence.java * 日期:2014-09-02 * 程序功能:LCS(不连续) * 版权:CopyRight@A2BGeek * 作者:A2BGeek */ public class LCSequence { private String mOne, mTwo; int[][] mMatrix; int[][] mB; String mResult; public LCSequence(String one, String two) { mOne = one; mTwo = two; int lengthOne = one.length(); int lengthTwo = two.length(); mMatrix = new int[lengthOne + 1][lengthTwo + 1]; mB = new int[lengthOne + 1][lengthTwo + 1]; mResult = ""; } public void generateMatrix() { int lengthOne = mOne.length(); int lengthTwo = mTwo.length(); for (int i = 1; i <= lengthOne; i++) { mMatrix[i][0] = 0; } for (int j = 1; j <= lengthTwo; j++) { mMatrix[0][j] = 0; } mMatrix[0][0] = 0; // 1 stands for upleft, 2 stands for up, 3 stands for left for (int i = 1; i <= lengthOne; i++) { for (int j = 1; j <= lengthTwo; j++) { if (mOne.charAt(i - 1) == mTwo.charAt(j - 1)) { mMatrix[i][j] = mMatrix[i - 1][j - 1] + 1; mB[i][j] = 1; } else if (mMatrix[i - 1][j] >= mMatrix[i][j - 1]) { mMatrix[i][j] = mMatrix[i - 1][j]; mB[i][j] = 2; } else if (mMatrix[i - 1][j] < mMatrix[i][j - 1]) { mMatrix[i][j] = mMatrix[i][j - 1]; mB[i][j] = 3; } } } } public void getLCSequence(String str, int i, int j) { if (i == 0 || j == 0) { return; } if (mB[i][j] == 1) { getLCSequence(str, i - 1, j - 1); mResult += str.charAt(i - 1); } else if (mB[i][j] == 2) { getLCSequence(str, i - 1, j); } else { getLCSequence(str, i, j - 1); } } public void printMatrix(int[][] in) { for (int i = 0; i < in.length; i++) { for (int j = 0; j < in[i].length; j++) { System.out.print(in[i][j] + " "); } System.out.println(); } } public void printMatrix(char[][] in) { for (int i = 0; i < in.length; i++) { for (int j = 0; j < in[i].length; j++) { System.out.print(in[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { String one = "abcbdab"; String two = "bdcaba"; LCSequence mLcSequence = new LCSequence(one, two); mLcSequence.generateMatrix(); mLcSequence.printMatrix(mLcSequence.mMatrix); System.out.println("------------------------"); mLcSequence.printMatrix(mLcSequence.mB); mLcSequence.getLCSequence(one, one.length(), two.length()); System.out.println(mLcSequence.mResult); } }
【数据结构与算法】LCS(不连续)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。