当我们使用 Java 工作时，字符串操作和比较是日常任务。
字符串是原始字符的序列，在 Java 中，它包装在String类中。尽管两个字符串可能是不同的对象，但我们可以比较它们的内部字符并检查例如它们是否相等或包含共同模式。
1、字符串旋转是什么？
字符串的旋转是指包含相同字符但顺序不同的字符串。具体来说，一个或多个字符从原始位置移动。例如，字符串“cdab”是“abcd”的旋转。这可以分为两个步骤：
- abcd -> dabc将最后一个d移至第一个位置
- dabc -> cdab将最后一个c移至第一个位置
这是通过从右侧移动来完成的，但也可以从左侧完成。值得注意的是，我们可以说，如果两个字符串的长度不同，它们就不能是另一个字符串的一次旋转。
简单实现：
boolean doubledOriginContainsRotation(String origin, String rotation) {
if (origin.length() == rotation.length()) {
return origin.concat(origin)
.contains(rotation);
}
return false;
}
|
我们将原点与其自身连接起来，并检查它是否包含潜在的旋转：
return origin.concat(origin).contains(rotation);
我们看一下算法复杂度：
- 时间复杂度：O(n*m)，其中 n 是串联长度，m 是旋转长度
- 空间复杂度：O(n) 与字符串的长度成正比
算法改进
首先，我们收集原点起始字符旋转中的所有索引。最后，我们循环原点并比较移动位置的字符串。
一旦我们知道了公共字符，我们就可以检查字符串是否继续相等：
boolean isRotationUsingCommonStartWithOrigin(String origin, String rotation) {
if (origin.length() == rotation.length()) {
List<Integer> indexes = IntStream.range(0, origin.length())
.filter(i -> rotation.charAt(i) == origin.charAt(0))
.boxed()
.collect(Collectors.toList());
for (int startingAt : indexes) {
if (isRotation(startingAt, rotation, origin)) {
return true;
}
}
}
return false;
}
boolean isRotation(int startingAt, String rotation, String origin) {
for (int i = 0; i < origin.length(); i++) {
if (rotation.charAt((startingAt + i) % origin.length()) != origin.charAt(i)) {
return false;
}
}
return true;
}
|
有两个要点需要关注。第一个是我们收集索引的地方：
List<Integer> indexes = IntStream.range(0, origin.length())
.filter(i -> rotation.charAt(i) == origin.charAt(0))
.boxed()
.collect(Collectors.toList());
|
这些是旋转中我们可以找到原点起始字符的位置。然后，我们循环遍历字符串并检查移动的位置：
for (int i = 0; i < origin.length(); i++) {
if (rotation.charAt((startingAt + i) % origin.length()) != origin.charAt(i)) {
return false;
}
}
|
值得注意的是，当超过旋转长度时，我们使用模 (%) 从第一个索引返回。我们看一下算法复杂度：
- 时间复杂度：O(n*m)，其中 n 是原点的长度，m 是找到的索引的数量
- 空间复杂度：O(n)
前后缀旋转比较
如果我们找到原点和旋转的共同起始字符，我们也可以说我们的字符串在该匹配点之前和之后将相等。例如，我们的原始字符串“ abcd”在位置2处与“cdab”有共同的c。但是，对于字符串的其余部分，前缀和后缀需要相应地相等
每当我们找到一个共同字符时，我们就可以比较剩余字符段的前缀和后缀，反转原点和旋转：
boolean isRotationUsingSuffixAndPrefix(String origin, String rotation) {
if (origin.length() == rotation.length()) {
return checkPrefixAndSuffix(origin, rotation);
}
return false;
}
boolean checkPrefixAndSuffix(String origin, String rotation) {
if (origin.length() == rotation.length()) {
for (int i = 0; i < origin.length(); i++) {
if (origin.charAt(i) == rotation.charAt(0)) {
if (checkRotationPrefixWithOriginSuffix(origin, rotation, i)) {
if (checkOriginPrefixWithRotationSuffix(origin, rotation, i)) {
return true;
}
}
}
}
}
return false;
}
boolean checkRotationPrefixWithOriginSuffix(String origin, String rotation, int i) {
return origin.substring(i)
.equals(rotation.substring(0, origin.length() - i));
}
boolean checkOriginPrefixWithRotationSuffix(String origin, String rotation, int i) {
return origin.substring(0, i)
.equals(rotation.substring(origin.length() - i));
}
|
我们有两项检查要做。首先，我们比较旋转前缀和原点后缀：
return origin.substring(i)
.equals(rotation.substring(0, origin.length() - i));
|
然后，我们将旋转后缀与原点前缀进行比较：
return origin.substring(0, i)
.equals(rotation.substring(origin.length() - i));
|
值得注意的是，这些检查可以按任何顺序进行。
我们看一下算法复杂度：
- 时间复杂度：O(n*n) 比较两个长度为 n 的字符串
- 空间复杂度：O(n)
字符队列的旋转比较
该问题的另一种观点是将两个字符串想象为队列。然后，我们将旋转的顶部字符移到尾部，并将新队列与原点进行比较。
我们创建两个队列。然后，我们从顶部字符移动到旋转的底部，同时在每一步检查它是否等于原点。
boolean isRotationUsingQueue(String origin, String rotation) {
if (origin.length() == rotation.length()) {
return checkWithQueue(origin, rotation);
}
return false;
}
boolean checkWithQueue(String origin, String rotation) {
if (origin.length() == rotation.length()) {
Queue<Character> originQueue = getCharactersQueue(origin);
Queue<Character> rotationQueue = getCharactersQueue(rotation);
int k = rotation.length();
while (k > 0 && null != rotationQueue.peek()) {
k--;
char ch = rotationQueue.peek();
rotationQueue.remove();
rotationQueue.add(ch);
if (rotationQueue.equals(originQueue)) {
return true;
}
}
}
return false;
}
Queue<Character> getCharactersQueue(String origin) {
return origin.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.toCollection(LinkedList::new));
}
|
创建队列后，相关的是我们如何断言我们的字符串是相等的：
int k = rotation.length();
while (k > 0 && null != rotationQueue.peek()) {
k--;
char ch = rotationQueue.peek();
rotationQueue.remove();
rotationQueue.add(ch);
if (rotationQueue.equals(originQueue)) {
return true;
}
}
|
在恒定时间内将队列的顶部元素移动到底部为我们提供了一个新的移位对象来与原点进行比较。我们看一下算法复杂度：
- 时间复杂度：最坏情况是 O(n*n)，我们在与原点进行比较的同时遍历整个队列
- 空间复杂度：O(n)
2、镜像反射是什么？
一个常见的误解是，获得字符串的镜像反射只需颠倒其顺序即可。以字符串“ALL”为例。直觉上，人们可能会认为它的镜面反射是“LLA”。然而，通过使用实际镜子仔细检查，我们发现“LLA”与“ ALL ”的镜像版本不太匹配。
关键的误解在于，字符串中的每个单独字符都会在其镜像反射中经历反转。因此， “ALL”的镜面反射实际上显示为“⅃⅃A”。
因此，当我们说字符串等于其镜像反射时，它有两个要求：
- 该字符串仅包含对称字符。
- 给定的字符串必须等于其反转值。换句话说，字符串必须是回文，例如“ MUM ”
为简单起见，我们仅检查由大写英文字母组成的字符串值作为本教程的示例。然后，这些是我们需要检查的对称大写字符：
final static Set<Character> SYMMETRIC_LETTERS = Set.of('A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y');
接下来我们探讨一下如何进行String镜像反射检查。
现在我们了解了问题的两个要求，解决问题的一个简单想法是创建一种将对称字符检查和回文字符串检查结合起来的方法：
boolean isMirrorImageEqual(String input) {
return containsOnlySymmetricLetters(input) && isPalindrome(input);
}
|
接下来，让我们一步步解决这个问题。实现containsOnlySymmetricLetters()方法
由于我们已经在 Set 中定义了对称字母，因此我们需要检查SYMMETRIC_LETTERS是否包含给定String中的每个字符：
boolean containsOnlySymmetricLetters(String input) {
Set<Character> characterSet = input.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.toSet());
characterSet.removeAll(SYMMETRIC_LETTERS);
return characterSet.isEmpty();
}
|
如上面的代码所示，我们分三步执行此检查：
- 将输入字符串转换为名为characterSet的Set<Character>
- 从字符集中删除所有必需的对称字母
- 删除后检查characterSet是否为空
- 如果集合为空，则表示仅包含对称字符
接下来，我们来实现isPalindrome()方法。实现isPalindrome()方法
在 Java 中检查String是否为回文有不同的方法。让我们采用一个简单的解决方案来完成这项工作：
boolean isPalindrome(String input) {
String reversed = new StringBuilder(input).reverse()
.toString();
return input.equals(reversed);
}
|
正如我们所看到的，我们检查输入的 String和反转的输入是否相等，以确定输入是否是回文。