前言

String字符串在我们开发中非常高频出现的一种数据结构，我这里准备了几道小题，不管你是初学者还是专家，都可以试试是否可以很容易的解决下面几道题，如果你有更好的解决办法，欢迎在评论去交流！

1. 如何不使用Java内建方法反转一个字符串？
2. 写一个java程序检查两个字符串是异位词？【异位词是指相同字符不同位置】
3. 判断一个字符串中的所有字符是否只出现一次？
4. 如何从字符串中找到重复的字符?
5. 找到字符串的所有子字符串?
6. 找出一个输入字符串的所有排列可能？

再开始看下面的解法前不妨自己先想一想这几道题都应该怎么解决，然后看看下面的方法是不是和你想的一致，如果你的方法更好，欢迎在评论区留言。

如何不使用Java内建方法反转一个字符串？

解决这个问题有三种方式：

• 使用循环
• 使用递归
• 使用StringBuilder、StringBuffer

使用for循环

思路：

1. 声明一个空String变量，用来保存最终反转的字符串；
2. 使用for循环遍历要反转的字符串，从最后一个位置到第0个位置；
3. 在遍历时将字符添加到声明的空String变量上。

public class ReverseStringForMain {public static void main(String[] args) {String blogName = "小黑说Java";String reverse = "";for (int i = blogName.length() - 1; i >= 0; i--) {reverse = reverse + blogName.charAt(i);}System.out.println("Reverse of 小黑说Java is: " + reverse);}
}

使用递归

思路：

1. 如果字符串长度为1，则反转结果为该字符串本身；
2. 如果字符串长度大于1，则反转结果为该字符串的最后一个字符加剩余字符串的反转结果。

public class ReverseStringRecursive {public static void main(String[] args) {ReverseStringRecursive rsr = new ReverseStringRecursive();String blogName = "小黑说Java";String reverse = rsr.recursiveReverse(blogName);System.out.println("Reverse of 小黑说Java is:" + reverse);}public String recursiveReverse(String orig) {if (orig.length() == 1){return orig;}else{return orig.charAt(orig.length() - 1) + recursiveReverse(orig.substring(0, orig.length() - 1));}}
}

使用StringBuffer

使用StringBuffer的reverse方法，同样可以实现字符串的反转功能。

public class StringBufferReverse {public static void main(String[] args) {String blogName = "小黑说Java";StringBuffer sb = new StringBuffer(blogName);System.out.println("Reverse of 小黑说Java is:" + sb.reverse());}
}

写一个java程序检查两个字符串是异位词?

说明：异位词是指两个单词有相同的字母，但是顺序不同，如: Angel 和Angle。

这道题有多种解决方式：

• 使用String类的方法
• 使用Arrays.sort()
• 使用计数数组
• 使用Guava的Multiset

使用String类方法

思路：

1. 建立一个方法，接收两个字符串变量，用来判断是否是异位词；
2. 迭代第一个String单词，并使用charAt()方法从中获得char c；
3. 如果第二个String单词的indexOf(c)的值等于-1，那么两个字符串不是字谜；
4. 如果第二个String单词的indexOf(c)的值不等于-1，那么从第二个单词中删除字符c;
5. 如果第二个String单词最后是个空字符串，则代表两个单词是异位词。

public class StringAnagramMain {public static void main(String[] args) {String word = "小黑说Java";String anagram = "小黑说JAVA";System.out.println("小黑说Java and 小黑说JAVA are anagrams :" + isAnagramUsingStringMethods(word, anagram));}public static boolean isAnagramUsingStringMethods(String word, String anagram) {if (word.length() != anagram.length())return false;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);int index = anagram.indexOf(c);if (index != -1) {anagram = anagram.substring(0, index) + anagram.substring(index + 1, anagram.length());} else{return false;}}return anagram.isEmpty();}
}

使用Arrays.sort()

思路：直接对两个字符串排序，如果排序之后两个字符串相等，则表示两个字符串是异位词。

public class AnagramUsingSort {public static void main(String[] args) {String word = "小黑说Java";String anagram = "小黑说JAVA";System.out.println("小黑说Java and 小黑说JAVA are anagrams :" + isAnagramUsingArraySort(word, anagram));}public static boolean isAnagramUsingArraySort(String word, String anagram) {String sortedWord = sortChars(word);String sortedAnagram = sortChars(anagram);return sortedWord.equals(sortedAnagram);}public static String sortChars(String word) {char[] wordArr = word.toLowerCase().toCharArray();Arrays.sort(wordArr);return String.valueOf(wordArr);}
}

使用计数数组

思路：

1. 如果两个字符串长度不同，则不是异位词；
2. 创建一个长度为256的数组；
3. 迭代第一个字符串str1；
4. 在每次迭代中，我们递增第一个String str1的计数，递减第二个String str2的计数；
5. 如果任何字符的count在末尾不为0，则表示两个string不是字谜。

这种方法的时间复杂度是O(n)，但它需要额外的空间计数数组。

public class AnagramCountingMain {public static void main(String args[]){boolean isAnagram = isAnagram("Angle","Angel");System.out.println("Are Angle and Angel anangrams: "+isAnagram);}public static boolean isAnagram(String str1, String str2) {if (str1.length() != str2.length()) {return false;}int count[] = new int[256];for (int i = 0; i < str1.length(); i++) {count[str1.charAt(i)]++;count[str2.charAt(i)]--;}for (int i = 0; i < 256; i++) {if (count[i] != 0) {return false;}}return true;}
}

使用Guava的Multiset

如果您喜欢使用Guava库，那可以使用MultiSet来检查两个String是否为异位词。

MultiSet允许每个元素出现多次，并记录每个元素的计数。

当然这种方式需要在pom.xml添加Guava依赖。

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>27.1-jre</version>
</dependency>

代码如下：

import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multiset;public class AnagramMultiSet {public static void main(String args[]){boolean isAnagram = isAnagramMultiset("Angle","Angel");System.out.println("Are Angle and Angel anangrams: "+isAnagram);}public static boolean isAnagramMultiset(String str1, String str2) {if (str1.length() != str2.length()) {return false;}Multiset<Character> ms1 = HashMultiset.create();Multiset<Character> ms2 = HashMultiset.create();for (int i = 0; i < str1.length(); i++) {ms1.add(str1.charAt(i));ms2.add(str2.charAt(i));}return ms1.equals(ms2);}
}

判断一个字符串中的所有字符是否只出现一次？

说明：比如Apple单词中字符p出现多次，所以不符合；world中所有单词都只出现一次，所以符合。

这道题有以下几种解决方法：

• 使用HashSet
• 使用indexOf和lastIndexOf方法
• 使用字符的ascii值

使用HashSet

依赖于HashSet的add()方法，如果已存在的元素会返回false。

步骤：

1. 遍历每个字符，添加到HashSet；
2. 如果HashSet的add方法返回false，那么它不是所有的唯一字符。

public class StringAllUniqueCharMain {public static void main(String[] args) {System.out.println("Apple has all unique chars :"+ hasAllUniqueChars("apple"));System.out.println("index has all unique chars :"+ hasAllUniqueChars("index"));System.out.println("world has all unique chars :"+ hasAllUniqueChars("world"));}public static boolean hasAllUniqueChars (String word) {HashSet alphaSet=new HashSet();for(int index=0;index < word.length(); index ++)   {char c =word.charAt(index);if(!alphaSet.add(c))return false;}return true;}
}

使用indexOf和lastIndexOf方法

思路：如果indexOf和lastIndexOf对字符返回相同的值，则在该字符串中不会重复。

public class StringAllUniqueCharMain {public static void main(String[] args) {System.out.println("Apple has all unique chars : "+ hasAllUniqueChars("apple"));System.out.println("index has all unique chars : "+ hasAllUniqueChars("index"));System.out.println("world has all unique chars : "+ hasAllUniqueChars("world"));}public static boolean hasAllUniqueChars (String word) {for(int index=0;index < word.length(); index ++)   {char c =word.charAt(index);if(word.indexOf(c)!=word.lastIndexOf(c))return false;}return true;}
}

使用字符的ascii值

这个方法是最高效的。

思路：

1. 创建一个长度为26的布尔数组；
2. 将char转换为大写并获取其ascii值；
3. 将64减去ascii值以获得0到25之间的索引；
4. 如果字符不重复，则布尔数组中应该有false；

public class StringAllUniqueCharMain {public static void main(String[] args) {System.out.println("Apple has all unique chars : "+ hasAllUniqueChars("apple"));System.out.println("index has all unique chars : "+ hasAllUniqueChars("index"));System.out.println("world has all unique chars : "+ hasAllUniqueChars("world"));}public static boolean hasAllUniqueChars (String word) {boolean[] charMap = new boolean[26];for(int index=0;index < word.length(); index ++)   {// we are substracting char's ascii value to 64, so we get all index// from 0 to 25.int asciiCode = (int) word.toUpperCase().charAt(index) - 64;if(!charMap[asciiCode])charMap[asciiCode] = true;elsereturn false;}return true;}}

如何从字符串中找到重复的字符?

思路：

1. 创建一个HashMap，创建一个HashMap，字符串字符将作为key插入，其计数作为value插入;
2. 如果HashMap已经包含char，则将其计数增加1，否则将char放入HashMap中;
3. 如果Char的值大于1，这意味着它是该字符串中的重复字符。

import java.util.HashMap;public class StringFindDuplicatesMain {public static void main(String[] args) {String str = "juejin.com ";HashMap<Character, Integer> charCountMap = new HashMap<>();for (int i = 0; i < str.length(); i++) {char c = str.charAt(i);if (charCountMap.containsKey(c)) {charCountMap.put(c, charCountMap.get(c) + 1);} else {charCountMap.put(c, 1);}}for (Character c : charCountMap.keySet()) {if (charCountMap.get(c) > 1)System.out.println("duplicate character : " + c + " ====== " + " count : " + charCountMap.get(c));}}
}

找到字符串的所有子字符串?

例如:如果输入是abb，那么输出应该是a, b, b, ab, bb, abb

思路：使用String类的subString方法来查找所有subString。

class SubstringsOfStringMain{public static void main(String args[]){String str="abbc";System.out.println("All substring of abbc are:");for (int i = 0; i < str.length(); i++) {for (int j = i+1; j <= str.length(); j++) {System.out.println(str.substring(i,j));}}}
}

这个解决办法的时间复杂度为O(n^3)。因为我们有两个循环而且String的子字符串方法的时间复杂度是O(n)

如果想找到String的所有不同的子字符串，那么需要使用HashSet来删除重复的字符串。

找出一个输入字符串的所有排列可能？

比如：输入“AB”，输出["AB","BA"]，输入“ABC”，输出["ABC","ACB","BAC","BCA","CBA","CAB"]。

思路：

1. 取出String的第一个字符，递归输入剩余String的排列的不同位置；
2. 假设输入String为ABC，取出第一个字符"A"；
3. 从BC中取出B，将剩余字符串"C"递归输入；
4. String长度为1时，返回，所以返回“C”；
5. 将取出的“B”分别插入到递归返回结果的字符串的每一个位置；
6. 这时得到BC,CB，返回;
7. 将取出的字符“A”分别插入返回结果的字符串的每一个位置；
8. 这时得到[ABC,BAC,BCA]和[ACB,CAB,CBA]；
9. 最终返回结果就是ABC的所有排序。

import java.util.HashSet;
import java.util.Set;public class PermutationOfStringJava {public static void main(String[] args) {Set<String> set = permutationOfString("ABC");System.out.println("Permutations of String ABC are:");for (String str : set) {System.out.println(str);}}public static Set<String> permutationOfString(String str) {Set<String> permutationSet = new HashSet<>();if (str.length() == 1) {permutationSet.add(str);return permutationSet;}char c = str.charAt(0);String rem = str.substring(1);Set<String> permutatedSetForRemainingString = permutationOfString(rem);for (String permutedString : permutatedSetForRemainingString) {for (int j = 0; j <= permutedString.length(); j++) {String permutation = insertFirstCharAtDiffPlaces(permutedString, c, j);permutationSet.add(permutation);}}return permutationSet;}public static String insertFirstCharAtDiffPlaces(String perm, char firstChar, int index) {return perm.substring(0, index) + firstChar + perm.substring(index);}
}

小结

以上就是本期的所有内容，怎么样，这些方法你都想到了吗？如果你有更好的方法欢迎留言交流。

如果对你有帮助，点个赞是对我最大的鼓励。