Skip to content

Commit 58ee959

Browse files
BlankjBlankj
committed
feat: update 005
1 parent 5765dbc commit 58ee959

File tree

2 files changed

+89
-29
lines changed

2 files changed

+89
-29
lines changed

‎note/005/README.md

+25-8
Original file line numberDiff line numberDiff line change
@@ -103,27 +103,44 @@ class Solution {
103103

104104
## 背景
105105

106-
给定一个字符串，求出其最长回文子串。例如：
106+
给定一个字符串，求出其最长回文子串（回文字符串就是从左到右读和从右往左读完全一样，也就是字符串关于中间对称）。例如：
107107

108108
1. s = "babad"，最长回文长度为 `3`，可以是 `bab` 或者 `aba`；
109109
2. s = "cbbda"，最长回文长度为 `2`，即 `bb`；
110110
3. s = "abcde"，最长回文长度为 `1`，即单个字符本身。
111111

112-
等同于LeetCode上的第五题：[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring)
112+
这个问题等同于LeetCode上的 [Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring)。
113113

114114
其相关题解可以查看这里：[传送门](https://github.com/Blankj/awesome-java-leetcode/blob/master/note/005/README.md)
115115

116-
以上问题的传统思路大概是，遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为 `O(n2)`，效率很差。
116+
以上问题的传统思路大概是遍历每一个字符，以该字符为中心向两边查找，其时间复杂度为 `O(n2)`，效率很差。
117117

118-
1975 年，一个叫 Manacher 的人发明了一个算法，Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到 `O(n)`。下面来看看马拉车算法是如何工作的。
118+
1975年，一个叫 Manacher 的人发明了一个算法，Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到 `O(n)`，下面按我理解的思路来讲解其原理。
119119

120-
最后一种思路那就是 `Manacher's Algorithm`，中文名叫马拉车算法，该算法就是专为解决此问题而发明的，其时间复杂度提升到了线性。下面我以我理解的思路来讲解其原理。
121120
由于回文串的奇偶行不确定，比如 `lol` 是奇回文，而 `lool` 是偶回文，马拉车算法的第一步就是对其进行预处理，做法就是在每个字符两侧都加上一个特殊字符，一般就是不会出现在原串中的即可，我们可以选取 `#`，那么
122121

123-
`lol` -> `#l#o#l#`
124-
`lool` -> `#l#o#o#l#`
122+
```
123+
lol -> #l#o#l#
124+
lool -> #l#o#o#l#
125+
```
126+
127+
这样处理后，不管原来字符串长度是奇数还是偶数，最终得到的长度都将是奇数，从而能把两种情况合并起来一起考虑，记预处理后的字符串为 `str`。
128+
129+
我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。
130+
131+
马拉车算法定义了一个回文半径数组 `len`，用 `len[i]` 表示以第 `i` 个字符为对称轴的回文串的回文半径，比如以 `str[i]` 为中心的最长回文串是 `str[l, r]`，那么 `len[i] = r - i + 1`
132+
133+
我们以 `lollool` 为例，参看下表。
134+
135+
| str | # | l | # | o | # | l | # | l | # | o | # | o | # | l | # |
136+
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
137+
| len | 1 | 2 | 1 | 4 | l | 2 | 3 | 2 | 1 | 2 | 5 | 2 | 1 | 2 | 1 |
138+
139+
可以发现 `len[i] - 1` 就等于该回文串在原串中的长度。
140+
141+
证明：在转换后的字符串 `str` 中，那么对于以 `str[i]` 为中心的最长回文串的长度为 `2 * len[i] - 1`,其中又有 `len[i]` 个分隔符，所以在原字符串中的长度就是 `len[i] - 1`。
125142

126-
这样处理后不管原来字符串长度是奇还是偶，最终得到的长度都将是奇数，这样就能把两种情况合并起来考虑。
143+
那么我们剩下的工作就是求 `len` 数组
127144

128145

129146

‎src/com/blankj/hard/_044/Solution.java

+64-21
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,9 @@
11
package com.blankj.hard._044;
22

3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
37
/**
48
* <pre>
59
* author: Blankj
@@ -30,35 +34,74 @@ public class Solution {
3034
// return pi == pl;
3135
// }
3236

33-
public boolean isMatch(String s, String p) {
34-
if (p.length() == 0) return s.length() == 0;
35-
int sl = s.length(), pl = p.length();
36-
boolean[][] dp = new boolean[sl + 1][pl + 1];
37-
char[] sc = s.toCharArray(), pc = p.toCharArray();
38-
dp[0][0] = true;
39-
for (int i = 1; i <= pl; ++i) {
40-
if (pc[i - 1] == '*') dp[0][i] = dp[0][i - 1];
37+
// public boolean isMatch(String s, String p) {
38+
// if (p.length() == 0) return s.length() == 0;
39+
// int sl = s.length(), pl = p.length();
40+
// boolean[][] dp = new boolean[sl + 1][pl + 1];
41+
// char[] sc = s.toCharArray(), pc = p.toCharArray();
42+
// dp[0][0] = true;
43+
// for (int i = 1; i <= pl; ++i) {
44+
// if (pc[i - 1] == '*') dp[0][i] = dp[0][i - 1];
45+
// }
46+
// for (int i = 1; i <= sl; ++i) {
47+
// for (int j = 1; j <= pl; ++j) {
48+
// if (pc[j - 1] != '*') {
49+
// dp[i][j] = dp[i - 1][j - 1] && (sc[i - 1] == pc[j - 1] || pc[j - 1] == '?');
50+
// } else {
51+
// dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
52+
// }
53+
// }
54+
// }
55+
// return dp[sl][pl];
56+
// }
57+
58+
public List<String> fullJustify(String[] words, int maxWidth) {
59+
int len = words.length;
60+
if (len == 0) return Collections.emptyList();
61+
List<String> ans = new ArrayList<>();
62+
StringBuilder spaces = new StringBuilder();
63+
for (int i = 0; i < maxWidth; ++i) {
64+
spaces.append(" ");
4165
}
42-
for (int i = 1; i <= sl; ++i) {
43-
for (int j = 1; j <= pl; ++j) {
44-
if (pc[j - 1] != '*') {
45-
dp[i][j] = dp[i - 1][j - 1] && (sc[i - 1] == pc[j - 1] || pc[j - 1] == '?');
66+
int sLen = -1, left = 0;
67+
for (int i = 0; i < len; ++i) {
68+
if (sLen + words[i].length() + 1 <= maxWidth) {
69+
sLen += words[i].length() + 1;
70+
} else {
71+
StringBuilder sub = new StringBuilder(words[left]);
72+
int rest = maxWidth - sLen;
73+
int seg = i - left;
74+
if (seg == 0) {
75+
sub.append(spaces.substring(0, rest));
4676
} else {
47-
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
77+
int leastSpace = rest / seg + 1;
78+
int restSpace = rest % seg;
79+
for (int j = left + 1; j < i; ++j) {
80+
if (restSpace-- > 0) {
81+
sub.append(spaces.substring(0, leastSpace + 1)).append(words[j]);
82+
} else {
83+
sub.append(spaces.substring(0, leastSpace)).append(words[j]);
84+
}
85+
}
4886
}
87+
ans.add(sub.toString());
88+
left = i;
89+
sLen = words[i].length();
4990
}
5091
}
51-
return dp[sl][pl];
92+
StringBuilder sub = new StringBuilder(words[left]);
93+
for (int i = left + 1; i < len; ++i) {
94+
sub.append(" ").append(words[i]);
95+
}
96+
ans.add(sub + spaces.substring(0, maxWidth - sub.length()));
97+
return ans;
5298
}
5399

100+
54101
public static void main(String[] args) {
55102
Solution solution = new Solution();
56-
System.out.println(solution.isMatch("aa", "a")); // false
57-
System.out.println(solution.isMatch("aa", "aa")); // true
58-
System.out.println(solution.isMatch("aaa", "aa")); // false
59-
System.out.println(solution.isMatch("aa", "*")); // true
60-
System.out.println(solution.isMatch("aa", "a*")); // true
61-
System.out.println(solution.isMatch("ab", "?*")); // true
62-
System.out.println(solution.isMatch("aab", "c*a*b"));// false
103+
System.out.println(solution.fullJustify(new String[]{"", ""}, 0));
104+
System.out.println(solution.fullJustify(new String[]{"a"}, 1));
105+
System.out.println(solution.fullJustify(new String[]{"This", "is", "an", "example", "of", "text", "justification."}, 16));
63106
}
64107
}

0 commit comments

Comments
 (0)