【数据结构与算法】LCS（不连续）

深藏阁楼爱情的钟 2022-08-11 19:00 99阅读 0赞

这个问题很经典，典型的动态规划，动态规划就是填一个表，然后遍历一下就行了。

*  代码实现

/**
     * 源码名称：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);
    	}
    }