6道String练习题，你会做吗？

发表于

这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战

前言

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

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

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

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

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

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

使用for循环

思路：

  1. 声明一个空String变量，用来保存最终反转的字符串；
  2. 使用for循环遍历要反转的字符串，从最后一个位置到第0个位置；
  3. 在遍历时将字符添加到声明的空String变量上。
1
2
3
4
5
6
7
8
9
10
java复制代码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，则反转结果为该字符串的最后一个字符加剩余字符串的反转结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码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方法，同样可以实现字符串的反转功能。

1
2
3
4
5
6
7
java复制代码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单词最后是个空字符串，则代表两个单词是异位词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码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()

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
java复制代码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)，但它需要额外的空间计数数组。

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
java复制代码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依赖。

1
2
3
4
5
xml复制代码<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>27.1-jre</version>
</dependency>

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码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，那么它不是所有的唯一字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
java复制代码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对字符返回相同的值，则在该字符串中不会重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码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；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码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;
          else
             return false;
     }
     return true;
 }
 
}

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

思路：

  1. 创建一个HashMap，创建一个HashMap，字符串字符将作为key插入，其计数作为value插入;
  2. 如果HashMap已经包含char，则将其计数增加1，否则将char放入HashMap中;
  3. 如果Char的值大于1，这意味着它是该字符串中的重复字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
java复制代码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。

1
2
3
4
5
6
7
8
9
10
11
java复制代码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的所有排序。
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
java复制代码
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);
    }
}

小结

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

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

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%