leetcode 1143: 최대 공통 하위 시퀀스

leetcode 1143: 최대 공통 하위 시퀀스


제목 설명: 두 개의 하위 서열의 가장 긴 공통 하위 서열을 구합니다
입력: text1 = "abcde",text2 = "ace"출력: 3 설명: 가장 긴 공통 서열은 "ace"이며 길이는 3 입니다.
문제풀이 단계: leetcode 516: 최장 회문 서열과 유사합니다.
1. 상태 정의: dp[i][j]에서 i는 문자열 1의 전 i 문자를 나타내고, j는 문자열 2의 전 j 문자를 나타내며, dp[i][j]는 s1[0...i]과 s2[0...j]의 가장 긴 공통 서열을 나타낸다.dp[len1+1][len2+1]
2. 상태 이동 방정식:
만약 s1[i]=s2[j]라면 이 문자는 가장 긴 공공 서열에 추가해야 합니다. dp[i][j]=dp[i-1][j-1]+1
하면, 만약, 만약...s2[j]는 dp[i][j]=max(dp[i-1][j], dp[i][j-1])
3. 초기화: dp[0][j]와 dp[i][0]는 모두 빈 문자열과 문자열 s의 공통 서열을 표시하고 길이는 0으로 설정한다.
4, 출력: dp[len1][len2]
코드:
    public int longestCommonSubsequence(String text1, String text2) {
    	int[][] dp = new int[text1.length()+1][text2.length()+1];
    	for (int i = 1; i <= text1.length(); i++) {
			for (int j = 1; j <= text2.length(); j++) {
				if(text1.charAt(i-1)==text2.charAt(j-1))
					dp[i][j] = dp[i-1][j-1]+1;
				else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
    	for (int i = 0; i < dp.length; i++) {
			System.out.println(Arrays.toString(dp[i]));
		}
    	return dp[text1.length()][text2.length()];
    }

좋은 웹페이지 즐겨찾기