[코딩인터뷰 완전정복] 1.5 하나 빼기

Q : 문자열 두개가 주어졌을 때, 문자열을 같게 만들기 위한 편집횟수가 1회 이내인지 확인하는 함수를 작성하라.

 

가능한 편집 = 문자 삽입, 문자 삭제, 문자 교체

#include <iostream>

bool CheckChange(char str1[], char str2[], int len1, int len2) {
	if (len1 - len2 > 1 || len2 - len1 > 1) return false;

	int maxLength = len1 > len2 ? len1 : len2;
	int change = 0;
	int insert = 0;
	int remove = 0;

	if (len1 == len2) {
		for (int i = 0; i < maxLength; i++) {
			if (str1[i] == str2[i]) continue;
			else if (change > 0) return false;
			else change++;
		}
	}
	else {
		for (int i = 0; i < maxLength; i++) {
			if (str1[i] == str2[i + insert - remove]) continue;
			else if (insert + remove > 0) return false;
			else if (str1[i] == str2[i + 1]) insert++;
			else if (str1[i + 1] == str2[i]) remove++;
			else return false;
		}
	}

	return true;
}

int main() {
	char input1[5] = { 'a','b','c','d','\0' };
	char input2[5] = { 'a','b','e','d','\0' };
	char input3[6] = { 'a','b','c','d','e','\0' };
	char input4[4] = { 'a','c','d','\0' };

	printf("%d\n", CheckChange(input1, input2, 5, 5 ));
	printf("%d\n", CheckChange(input1, input3, 5, 6));
	printf("%d\n", CheckChange(input1, input4, 5, 4));
	printf("%d\n", CheckChange(input2, input3, 5, 6));
}

길이가 2이상 차이날 경우 false

 

길이가 같을 경우 각 문자열을 순회하며 달라진 문자가 있는지 확인. 2개 이상일 경우 false

 

길이가 다를 경우 삽입 삭제가 이루어 졌는지 확인. 2번이상 변화가 있을경우 false

 

 

 

 

문자열을 길이로 정렬하여 삽입 삭제 확인을 통합가능.

 

다른 문자가 검출됐을때 문자열의 길이를 확인하면 문자 교체도 통합가능.

통합할경우 가독성은 낮아지지만 간결해짐. 시간복잡도는 같음