교차 문자열 자바 구현
2941 단어 알고리즘
샘플: s1 = "aabcc" s2 = "dbbca" - s3 = "aadbbcbcac", true 를 되 돌려 줍 니 다. - s3 = "aadbbbaccc", false 를 되 돌려 줍 니 다.
도전: 시간 복잡 도 O (n ^ 2) 또는 더 좋 음 요구
사고방식: 동적 기획 사상 으로 해결한다.동적 계획 배열 을 dp [i] [j] 로 정의 합 니 다. 그 중에서 s1 은 앞 i 위 를 취하 지만 i 는 이전 문자열 로 s3 를 구성 해 야 합 니 다.s2 는 앞의 j 위 를 취하 지만 J 위 이전의 문자열 도 s3 를 구성 해 야 합 니 다. s3 의 앞 i + j 위 를 구성 할 수 있 습 니까?먼저 문자열 s3 는 s1 또는 s2 로 시작 합 니 다. 해당 하 는 문자 가 같 으 면 할당 값 은 true 입 니 다. s1 이 비어 있다 고 가정 하면 s2 는 각각 s3 와 일치 하여 dp [0] [j] 를 넣 습 니 다.s2 가 비어 있다 고 가정 하면 s1 한 명 이 s3 와 일치 하여 dp [i] [0] 을 넣 습 니 다.코드 는 다음 과 같 습 니 다:
public boolean isInterleave(String s1, String s2, String s3)
{
int len1 = s1.length(), len2 = s2.length();
if (len1 + len2 != s3.length())
return false;
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
int i = 1, j = 1;
while (i <= len1 && s1.charAt(i - 1) == s3.charAt(i - 1))
dp[i++][0] = true;
while (j <= len2 && s2.charAt(j - 1) == s3.charAt(j - 1))
dp[0][j++] = true;
for (i = 1; i <= len1; i++) {
for (j = 1; j <= len2; j++) {
if ((dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
|| (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)))
dp[i][j] = true;
}
}
return dp[len1][len2];
}블 로그 참조: 동적 계획 - - 두 문자열 이 교차 하여 세 번 째 문 자 를 구성 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
