[Algorithm] Palindrome Check

  오늘 다뤄볼 상황은 문자열이 주어졌을 때, Palindrome 인지 아닌지 Check 하는 것이다. Palindrome 이란 String 을 거꾸로 뒤집었을 때 원본이랑 동일한 것을 의미한다. 예를 들어 abcdcba 는 reverse 해도 abcdcba 이므로 Palindrome 이다. 어떻게 알고리즘을 구성할 수 있을까?

 

  가장 먼저 떠올릴 수 있는 풀이는 실제로 문자열을 뒤집은 다음 원래 문자열과 비교해서 같은지 아닌지를 판단하는 것이다. 아래와 같이 코드를 작성할 수 있다.

using namespace std;

// time  : O(N)
// space : O(N)

bool isPalindrome(string str) {
	// Write your code here.
	string reverse = "";
	for (int i = str.size() - 1; i >= 0; i--) {
		reverse.push_back(str[i]);
	}
	if (str == reverse) return true;
	return false;
}

위와 같이 작성한 경우, 시간 복잡도 O(N) 공간복잡도 O(N) 에 해결할 수 있다.

 

  보다 효율적인 방법은 투포인터 알고리즘을 이용하는 것이다. 문자열의 시작과 끝의 인덱스를 의미하는 left 와 right 를 이용하여 string[left] 와 string[right] 를 비교하는 것이다. 코드는 아래와 같으며 시간 복잡도 O(N), 공간 복잡도 O(1) 에 해결할 수 있다.

using namespace std;

// time  : O(N)
// space : O(1)
bool isPalindrome(string str) {
	// Write your code here.
	int left = 0; int right = str.size() - 1;
	while (left < right) {
		if (str[left++] != str[right--]) return false;
	}
	return true;
}

 

https://github.com/versatile0010/AlgoExpert

GitHub - versatile0010/AlgoExpert: Solutions to AlgoExpert Problems.