11 检查字符串是否为回文
作为一个快速的提醒，回文（无论是字符串还是数字）在反转时看起来是不变的。这意味着可以从两个方向处理（读取）回文，并且将获得相同的结果（例如，单词madam是回文，而单词madam不是）。
一个易于实现的解决方案是用中间相遇的方法比较给定字符串的字母。基本上，此解决方案将第一个字符与最后一个字符进行比较，第二个字符与最后一个字符逐个进行比较，依此类推，直到到达字符串的中间。实现依赖于while语句：
public static boolean isPalindrome(String str) { int left = 0; int right = str.length() - 1; while (right > left) { if (str.charAt(left) != str.charAt(right)) { return false; } left++; right--; } return true; }
以更简洁的方法重写上述解决方案将包括依赖于for语句而不是while语句，如下所示：
public static boolean isPalindrome(String str) { int n = str.length(); for (int i = 0; i < n / 2; i++) { if (str.charAt(i) != str.charAt(n - i - 1)) { return false; } } return true; }
但是这个解决方案可以简化为一行代码吗？答案是肯定的。
JavaAPI 提供了StringBuilder类，该类使用reverse()方法。顾名思义，reverse()方法返回相反的给定字符串。对于回文，给定的字符串应等于它的反向版本：
public static boolean isPalindrome(String str) { return str.equals(new StringBuilder(str).reverse().toString()); }
在 Java8 函数风格中，也有一行代码用于此。只需定义从 0 到给定字符串一半的IntStream，并使用noneMatch()短路终端操作和谓词，按照中间相遇的方法比较字母：
public static boolean isPalindrome(String str) { return IntStream.range(0, str.length() / 2) .noneMatch(p -> str.charAt(p) != str.charAt(str.length() - p - 1)); }
现在，让我们讨论从给定字符串中删除重复字符。
12 删除重复字符
让我们从依赖于StringBuilder的这个问题的解决方案开始。解决方案主要应该循环给定字符串的字符，并构造一个包含唯一字符的新字符串（不可能简单地从给定字符串中删除字符，因为在 Java 中，字符串是不可变的）。
StringBuilder类公开了一个名为indexOf()的方法，该方法返回指定子字符串（在本例中是指定字符）第一次出现的给定字符串中的索引。因此，这个问题的一个潜在解决方案是，每次应用于当前字符的indexOf()方法返回 -1（这个负数意味着StringBuilder不包含当前字符）时，循环给定字符串的字符并将它们逐个添加到StringBuilder：
public static String removeDuplicates(String str) { char[] chArray = str.toCharArray(); // or, use charAt(i) StringBuilder sb = new StringBuilder(); for (char ch : chArray) { if (sb.indexOf(String.valueOf(ch)) == -1) { sb.append(ch); } } return sb.toString(); }
下一个解决方案依赖于HashSet和StringBuilder之间的协作。主要是，HashSet确保消除重复，而StringBuilder存储结果字符串。如果HashSet.add()返回true，那么我们也在StringBuilder中添加字符：
public static String removeDuplicates(String str) { char[] chArray = str.toCharArray(); StringBuilder sb = new StringBuilder(); Set<Character> chHashSet = new HashSet<>(); for (char c: chArray) { if (chHashSet.add(c)) { sb.append(c); } } return sb.toString(); }
到目前为止，我们提供的解决方案使用toCharArray()方法将给定字符串转换为char[]。或者，两种解决方案也可以使用str.charAt(position)。
第三种解决方案依赖于 Java8 函数式风格：
public static String removeDuplicates(String str) { return Arrays.asList(str.split("")).stream() .distinct() .collect(Collectors.joining()); }
首先，解决方案将给定的字符串转换为Stream<String>，其中每个条目实际上是一个字符。此外，该解决方案应用了有状态的中间操作distinct()。此操作将从流中消除重复项，因此它返回一个没有重复项的流。最后，该解决方案调用了collect()终端操作并依赖于Collectors.joining()，它只是将字符按照相遇顺序连接成一个字符串。
13 删除给定字符
依赖于 JDK 支持的解决方案可以利用String.replaceAll()方法。此方法将给定字符串中与给定正则表达式（在本例中，正则表达式是字符本身）匹配的每个子字符串（在本例中，每个字符）替换为给定的替换（在本例中，替换为空字符串，""）：
public static String removeCharacter(String str, char ch) { return str.replaceAll(Pattern.quote(String.valueOf(ch)), ""); }
注意，正则表达式被包装在Pattern.quote()方法中。这是转义特殊字符所必需的，例如“<，（，[，{，\，^，-，=，$，！”！, |, ], }, ), ?、*、+、、和>。该方法主要返回指定字符串的文本模式字符串。
现在，让我们来看一个避免正则表达式的解决方案。这一次，解决方案依赖于StringBuilder。基本上，解决方案循环给定字符串的字符，并将每个字符与要删除的字符进行比较。每次当前字符与要删除的字符不同时，都会在StringBuilder中追加当前字符：
public static String removeCharacter(String str, char ch) { StringBuilder sb = new StringBuilder(); char[] chArray = str.toCharArray(); for (char c : chArray) { if (c != ch) { sb.append(c); } } return sb.toString(); }
最后，让我们关注 Java8 函数式方法。这是一个四步方法：
- 通过
String.chars()方法将字符串转换成IntStream - 过滤
IntStream消除重复 - 将结果
IntStream映射到Stream<String> - 将此流中的字符串连接起来，并将它们收集为单个字符串
此解决方案的代码可以编写如下：
public static String removeCharacter(String str, char ch) { return str.chars() .filter(c -> c != ch) .mapToObj(c -> String.valueOf((char) c)) .collect(Collectors.joining()); }
或者，如果我们想要移除 Unicode 代理项对，那么我们可以依赖于codePointAt()和codePoints()，如下面的实现所示：
public static String removeCharacter(String str, String ch) { int codePoint = ch.codePointAt(0); return str.codePoints() .filter(c -> c != codePoint) .mapToObj(c -> String.valueOf(Character.toChars(c))) .collect(Collectors.joining()); }
对于第三方库支持，请考虑 ApacheCommonsLang，StringUtils.remove()。
现在，让我们来谈谈如何找到最形象的字符。
14 寻找最形象的字符
一个非常简单的解决方案依赖于HashMap。此解决方案包括三个步骤：
- 首先，循环给定字符串的字符，并将键值对放入
HashMap，其中键是当前字符，值是当前出现的次数 - 其次，计算
HashMap中表示最大出现次数的最大值（例如，使用Collections.max()） - 最后，通过循环
HashMap条目集，得到出现次数最多的字符
工具方法返回Pair<Character, Integer>，其中包含出现次数最多的字符和出现次数（注意，忽略了空格）。如果你不喜欢这个额外的类，也就是说，Pair，那就依赖Map.Entry<K, V>：
public static Pair<Character, Integer> maxOccurenceCharacter( String str) { Map<Character, Integer> counter = new HashMap<>(); char[] chStr = str.toCharArray(); for (int i = 0; i < chStr.length; i++) { char currentCh = chStr[i]; if (!Character.isWhitespace(currentCh)) { // ignore spaces Integer noCh = counter.get(currentCh); if (noCh == null) { counter.put(currentCh, 1); } else { counter.put(currentCh, ++noCh); } } } int maxOccurrences = Collections.max(counter.values()); char maxCharacter = Character.MIN_VALUE; for (Entry<Character, Integer> entry: counter.entrySet()) { if (entry.getValue() == maxOccurrences) { maxCharacter = entry.getKey(); } } return Pair.of(maxCharacter, maxOccurrences); }
如果使用HashMap看起来很麻烦，那么另一个解决方案（稍微快一点）就是依赖 ASCII 代码。此解决方案从 256 个索引的空数组开始（256 是扩展 ASCII 表代码的最大数目；更多信息可在“查找第一个非重复字符”部分中找到）。此外，此解决方案循环给定字符串的字符，并通过增加此数组中的相应索引来跟踪每个字符的出现次数：
private static final int EXTENDED_ASCII_CODES = 256; ... public static Pair<Character, Integer> maxOccurenceCharacter( String str) { int maxOccurrences = -1; char maxCharacter = Character.MIN_VALUE; char[] chStr = str.toCharArray(); int[] asciiCodes = new int[EXTENDED_ASCII_CODES]; for (int i = 0; i < chStr.length; i++) { char currentCh = chStr[i]; if (!Character.isWhitespace(currentCh)) { // ignoring space int code = (int) currentCh; asciiCodes[code]++; if (asciiCodes[code] > maxOccurrences) { maxOccurrences = asciiCodes[code]; maxCharacter = currentCh; } } } return Pair.of(maxCharacter, maxOccurrences); }
我们将在这里讨论的最后一个解决方案依赖于 Java8 函数式风格：
public static Pair<Character, Long> maxOccurenceCharacter(String str) { return str.chars() .filter(c -> Character.isWhitespace(c) == false) // ignoring space .mapToObj(c -> (char) c) .collect(groupingBy(c -> c, counting())) .entrySet() .stream() .max(comparingByValue()) .map(p -> Pair.of(p.getKey(), p.getValue())) .orElse(Pair.of(Character.MIN_VALUE, -1L)); }
首先，这个解决方案收集不同的字符作为Map中的键，以及它们的出现次数作为值。此外，它使用 Java8Map.Entry.comparingByValue()和max()终端操作来确定映射中具有最高值（最高出现次数）的条目。因为max()是终端操作，所以解决方案可以返回Optional<Entry<Character, Long>>，但是这个解决方案增加了一个额外的步骤，并将这个条目映射到Pair<Character, Long>。
15 按长度对字符串数组排序
排序时首先想到的是比较器的使用。
在这种情况下，解决方案应该比较字符串的长度，因此通过调用给定数组中每个字符串的String.length()来返回整数。因此，如果整数被排序（升序或降序），那么字符串将被排序。
JavaArrays类已经提供了一个sort()方法，该方法使用数组进行排序和一个比较器。在这种情况下，Comparator<String>应该完成这项工作。
在 Java7 之前，实现比较器的代码依赖于compareTo()方法。这种方法的常见用法是计算x1 - x2类型的差值，但这种计算可能导致溢出。这使得compareTo()相当乏味。从 Java7 开始，Integer.compare()就是一条路（没有溢出风险）。
下面是一个依赖于Arrays.sort()方法对给定数组排序的方法：
public static void sortArrayByLength(String[] strs, Sort direction) { if (direction.equals(Sort.ASC)) { Arrays.sort(strs, (String s1, String s2) -> Integer.compare(s1.length(), s2.length())); } else { Arrays.sort(strs, (String s1, String s2) -> (-1) * Integer.compare(s1.length(), s2.length())); } }
原始数字类型的每个包装器都有一个compare()方法。
从 Java8 开始，Comparator接口被大量有用的方法丰富了。其中一个方法是comparingInt()，它接受一个函数，该函数从泛型类型中提取int排序键，并返回一个Comparator<T>值，将其与该排序键进行比较。另一个有用的方法是reversed()，它反转当前的Comparator值。
基于这两种方法，我们可以授权Arrays.sort()如下：
public static void sortArrayByLength(String[] strs, Sort direction) { if (direction.equals(Sort.ASC)) { Arrays.sort(strs, Comparator.comparingInt(String::length)); } else { Arrays.sort(strs, Comparator.comparingInt(String::length).reversed()); } }
比较器可以用thenComparing()方法链接。
我们在这里给出的解决方案返回void，这意味着它们对给定的数组进行排序。为了返回一个新的排序数组而不改变给定的数组，我们可以使用 Java8 函数样式，如下代码片段所示：
public static String[] sortArrayByLength(String[] strs, Sort direction) { if (direction.equals(Sort.ASC)) { return Arrays.stream(strs) .sorted(Comparator.comparingInt(String::length)) .toArray(String[]::new); } else { return Arrays.stream(strs) .sorted(Comparator.comparingInt(String::length).reversed()) .toArray(String[]::new); } }
因此，代码从给定的数组中创建一个流，通过有状态的中间操作对其进行排序，并将结果收集到另一个数组中。
16 检查字符串是否包含子字符串
一个非常简单的一行代码解决方案依赖于String.contains()方法。
此方法返回一个boolean值，指示字符串中是否存在给定的子字符串：
String text = "hello world!"; String subtext = "orl"; // pay attention that this will return true for subtext="" boolean contains = text.contains(subtext);
或者，可以通过依赖于String.indexOf()（或String.lastIndexOf()来实现解决方案，如下所示：
public static boolean contains(String text, String subtext) { return text.indexOf(subtext) != -1; // or lastIndexOf() }
另一种解决方案可以基于正则表达式实现，如下所示：
public static boolean contains(String text, String subtext) { return text.matches("(?i).*" + Pattern.quote(subtext) + ".*"); }
注意，正则表达式被包装在Pattern.quote()方法中。这是转义特殊字符（如“<”）（[{^-=$）所必需的！|]})?*+. 给定子串中的>。
对于第三方库支持，请考虑 ApacheCommonsLang，StringUtils.containsIgnoreCase()。
17 计算字符串中子字符串的出现次数
计算一个字符串在另一个字符串中出现的次数是一个问题，它至少有两种解释：
- 11/111 发生 1 次
- 11/111 发生 2 次
在第一种情况下（111 中的 11 发生 1 次），可以依赖于String.indexOf()方法来解决。此方法的一种风格允许我们从指定的索引（如果没有这样的索引，则为 -1）开始获取指定子字符串第一次出现的字符串中的索引。基于此方法，该解决方案可以简单地遍历给定的字符串并计算给定子字符串的出现次数。遍历从位置 0 开始，直到找不到子字符串为止：
public static int countStringInString(String string, String toFind) { int position = 0; int count = 0; int n = toFind.length(); while ((position = string.indexOf(toFind, position)) != -1) { position = position + n; count++; } return count; }
或者，该溶液可以使用String.split()方法。基本上，该解决方案可以使用给定的子字符串作为分隔符来拆分给定的字符串。结果String[]数组的长度应等于预期出现的次数：
public static int countStringInString(String string, String toFind) { int result = string.split(Pattern.quote(toFind), -1).length - 1; return result < 0 ? 0 : result; }
在第二种情况下（111 中的 11 出现了 2 次），解决方案可以在一个简单的实现中依赖于Pattern和Matcher类，如下所示：
public static int countStringInString(String string, String toFind) { Pattern pattern = Pattern.compile(Pattern.quote(toFind)); Matcher matcher = pattern.matcher(string); int position = 0; int count = 0; while (matcher.find(position)) { position = matcher.start() + 1; count++; } return count; }
很好！让我们继续讨论字符串的另一个问题。
18 检查两个字符串是否为异序词
两个具有相同字符但顺序不同的字符串是异序词。一些定义强制要求字谜不区分大小写和/或应忽略空格（空格）。
因此，与应用的算法无关，解决方案必须将给定的字符串转换为小写并删除空格（空格）。除此之外，我们提到的第一个解决方案通过Arrays.sort()对数组进行排序，并通过Arrays.equals()检查它们的相等性。
一旦它们被排序，如果它们是字谜，它们将相等（下图显示了两个字谜）：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ktjouv9K-1657077108923)(https://github.com/apachecn/apachecn-java-zh/raw/master/docs/java-coding-prob/img/ebed6c7d-49fc-4c77-b4cf-f97de703e88e.png)]
此解决方案（包括其 Java8 函数式版本）在本书附带的代码中提供。这两种解决方案的主要缺点是排序部分。以下解决方案消除了这一步骤，并依赖于 256 个索引的空数组（最初仅包含 0）（字符的扩展 ASCII 表代码更多信息可在“查找第一个非重复字符”部分中找到）。
算法非常简单：
对于第一个字符串中的每个字符，此解决方案将此数组中对应于 ASCII 代码的值增加 1
对于第二个字符串中的每个字符，此解决方案将此数组中对应于 ASCII 代码的值减少 1
代码如下：
private static final int EXTENDED_ASCII_CODES = 256; ... public static boolean isAnagram(String str1, String str2) { int[] chCounts = new int[EXTENDED_ASCII_CODES]; char[] chStr1 = str1.replaceAll("\\s", "").toLowerCase().toCharArray(); char[] chStr2 = str2.replaceAll("\\s", "").toLowerCase().toCharArray(); if (chStr1.length != chStr2.length) { return false; } for (int i = 0; i < chStr1.length; i++) { chCounts[chStr1[i]]++; chCounts[chStr2[i]]--; } for (int i = 0; i < chCounts.length; i++) { if (chCounts[i] != 0) { return false; } } return true; }
在遍历结束时，如果给定的字符串是异序词，那么这个数组只包含 0。
