jotting

ⓁⒸ ‧‧‧ 647. Palindromic Substrings

Posted on | Post modified | In
回文子串

647. Palindromic Substrings 回文子串

❀ Origin

Problem

Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Note

  1. The input string length won’t exceed 1000.

Example 1

1
2
3
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2

1
2
3
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

❀ 翻譯

問題

給定一個字串, 你的任務是算出這個字串裡有幾個回文子串.
具有不同起始位置和結束位置的子字串符會被計算成不同的子字串, 即使他們包含著相同的字元.

注意

  1. 輸入字串的長度不會超過 1000.

❀ Solution

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {string} s
 * @return {number}
 */

var countSubstrings = function(s) {
	let len = s.length;
	let result_count = 0;

	/**
	 * 用 substr(start, length)
	 * 把所有可能的字串找出來,
	 * 再用 isPalindrome 判斷是不是回文子串
	 */
	for (let length = 1; length <= s.length; length++) {
		for (let start = 0; start <= s.length - length; start++) {
			let newStr = s.substr(start, length);
			if (isPalindrome(newStr)) result_count++;
		}
	}
	return result_count;
};

/**
 * 判斷字串是不是回文子串
 * 用鏡面位置去判斷是不是對稱,
 * 跑完都一樣就回傳 true
 */
var isPalindrome = (str)=> {
	for (let i = 0; i <= str.length - i - 1; i++) {
		if (str[i] !== str[str.length - i - 1]) return false;
	}
    return true;

	// if(str !==str.split('').reverse().join('')){
    //     return false;
    // }
    // return true;
};
console.log(countSubstrings('abcba'));

JavaScript II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string} s
 * @return {number}
 */
/**
 * Manacher's Algorithm
 * 還沒搞懂 好難
 */
var countSubstrings = function(s) {
    s = preprocess(s);
    console.log(s);
	let result = 0;
	for (let i = 0; i < s.length; i++) {
		let j = 0;
		while (j < s.length - i && i >= j && s[i + j] === s[i - j]) {
			//console.log(j);
			j++;
        }
        console.log('j/2: ', Math.trunc(j / 2));
        result += Math.trunc(j / 2);
        console.log(result);
	}
	return result;
};

var preprocess = function(s) {
	return '#' + s.split('').join('#') + '#';
};

console.log(countSubstrings('12212321'));

JavaScript III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * @param {string} s
 * @return {number}
 */
/**
 * LeetCode官方解答上最快的寫法, 感覺懂又不懂.
 *
 * 先以 i 為圓心算完後, 再以 i 和 i+1 的中心為圓心,
 * 這邊不太懂.
 *
 */
/**
 * 先以 i 為圓心, 往外擴展去判斷
 * 再以 i 和 i+1 的中心為圓心, 往外擴展去判斷
 *
 * 應該是基數長度與偶數長度的關係 目前未全部搞懂
 */

var countSubstrings = function(s) {
	let cnt = 0;

	for (let i = 0; i < s.length; i++) {
		console.log('i', i);
		cnt += countPalindrome(s, i, i) + countPalindrome(s, i, i + 1);
	}
	return cnt;
};

// 用start, end當圓心去擴展, 判斷 str[start] === str[end] 是否一樣, 回傳回文子串的數量
function countPalindrome(str, start, end) {
	let count = 0;

	/**
	 * 起始位置 start 不能比 0 小
	 * 結束位置 end 不能大於字串 str 的長度
	 *  str[start] === str[end]
	 * 上面三點才滿足回文字串的條件
	 * 因為判斷東西多, 用 while 會比較好寫
	 *
	 */
	while (start >= 0 && end < str.length && str[start] === str[end]) {
		console.log('start, end', start, end);

		// 往左一個位置
		start--;
		// 往右一個位置
		end++;
		// 回文字串數量加一
		count++;

		//繼續尋找回文子串
	}
	return count;
}
console.log(countSubstrings('abcdcba'));

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func countSubstrings(s string) int {
	count := 0
	for i := 0; i < len(s); i++ {
		// 統計以 i 為中心的回文總數
		count += countPalindrome(s, i, i)
		// 統計以當 i, i+1 為左右邊際時的中心，其回文總數
		count += countPalindrome(s, i, i+1)
	}
	return count
}

// 設定左右邊界，以中點為中心，往兩側擴展，
// 判斷是否為相同，相同即代表回文
// 回傳該中心往外的回文的總數
func countPalindrome(s string, left int, right int) int {
	var count int
	for left >= 0 && right < len(s) && s[left] == s[right] {
		count++
		left--
		right++
	}
	return count
}