์ฝ๋
class Solution {
public String longestPalindrome(String s) {
// ์ธ๋ฑ์ฑ์ ์ํ ๋ณ์
int left = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
// ํ์ ๊ธธ์ด ํฐ๋ฆฐ๋๋กฌ
int len1 = expandCenter(s, i, i);
// ์ง์ ๊ธธ์ด ํฐ๋ฆฐ๋๋กฌ
int len2 = expandCenter(s, i, i +1);
// ๋ ์ค ์ต๋ ๊ธธ์ด ์ ํ
int len = Math.max(len1, len2);
// ๊ธธ์ด๊ฐ ๋ ๊ธธ ๊ฒฝ์ฐ ์ธ๋ฑ์ค ์
๋ฐ์ดํธ
if (len > right - left) {
left = i - (len -1) / 2;
right = i + len / 2;
}
}
// ๊ฐ์ฅ ๊ธด ํฐ๋ฆฐ๋๋กฌ ๋ฆฌํด
return s.substring(left, right +1);
}
private int expandCenter(String s, int left, int right) {
// left์ right ์ธ๋ฑ์ค๊ฐ ๋ชจ๋ ๋ฒ์ ๋ด์ ์์ด์ผ ํ๋ฉฐ, ํฐ๋ฆฐ๋๋กฌ์ด์ด์ผ ํจ.
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
// ์กฐ๊ฑด ๋ง์กฑ ์ ๋ฒ์ ํ์ฅ
left--;
right++;
}
// ํ์ฅ ํ ๊ธธ์ด ๋ฐํ
return right - left -1;
}
}
Java
๋ณต์ฌ
๋ค๋ฅธ ํ์ด (from ์๊ตฌ๋ ์ฝ๋)
public class Ch06_06 {
public String longestPalindrome(String s) {
if (s.length() < 2) return s;
for (int windowSize = s.length(); windowSize > 1; windowSize--) {
for (int i = 0; i <= s.length() - windowSize; i++) {
if (isPalindrome(s, i, i + windowSize - 1)) {
return s.substring(i, i + windowSize);
}
}
}
return s.substring(0, 1);
}
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) return false;
start++;
end--;
}
return true;
}
}
Java
๋ณต์ฌ
์ด๋ ๊ฒ ์์ ํ์์ผ๋ก ์ง๊ด์ ์ผ๋ก ์งค์๋ ์์ง๋ง ์๊ฐ๋ณต์ก๋๊ฐ ์ข์ง ์๋ค.
๋ฌธ์ ํด๊ฒฐ ์์ด๋์ด
์ค์ํ์ฅ๋ฐฉ์์ ํ์ฉํ๋ ๋ฌธ์ ์ด๋ค. ๋ฒ์ ๋ด์์ ํฐ๋ฆฐ๋๋กฌ์ ๋ง๋ฌ์ ๋, ํด๋น ๋ถ๋ถ๋ถํฐ ํ์ฅ๋๋ ํฌ์ธํฐ๋ฅผ ๊ตฌํํ๋ ๋ก์ง์ด ํต์ฌ์ด๋ค.
๋ฌธ๋ฒ ์์ฒด๋ ์ด๋ ต์ง ์์ง๋ง ๋ฌธ์ ์ดํด ๋์ด๋๊ฐ ๋์๋ค.