This is the fourth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021
preface
String is a kind of data structure that appears very frequently in our development. I have prepared several questions here. Whether you are a beginner or an expert, you can try to see if you can easily solve the following questions.
- How do I invert a string without using Java built-in methods?
- Write a Java program that checks two strings for heterotopic words? 【 an allotopic is a different position of the same character 】
- Do all characters in a string appear only once?
- How do I find duplicate characters in a string?
- Find all the substrings of the string?
- Find all possible permutations of an input string?
Before you start looking at the solutions below, think about how you should solve each of these problems and see if they are consistent with what you think. If your solution is better, feel free to leave a comment in the comments section.
How do I invert a string without using Java built-in methods?
There are three ways to solve this problem:
- Using a loop
- Using a recursive
- Use StringBuilder and StringBuffer
Use the for loop
Ideas:
- Declare an empty String variable to hold the final reversed String;
- Use the for loop to iterate over the string to be reversed, from the last position to the 0th position;
- Adds characters to the declared empty String variable during traversal.
public class ReverseStringForMain {
public static void main(String[] args) {
String blogName = "Black says Java.";
String reverse = "";
for (int i = blogName.length() - 1; i >= 0; i--) {
reverse = reverse + blogName.charAt(i);
}
System.out.println("Reverse of Hei says Java is:"+ reverse); }}Copy the codeUsing a recursive
Ideas:
- If the string length is 1, the result is reversed to the string itself;
- If the string length is greater than 1, the inversion is the inversion of the last character of the string plus the rest of the string.
public class ReverseStringRecursive {
public static void main(String[] args) {
ReverseStringRecursive rsr = new ReverseStringRecursive();
String blogName = "Black says Java.";
String reverse = rsr.recursiveReverse(blogName);
System.out.println("Reverse of Hei says 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)); }}}Copy the codeUse StringBuffer
You can also reverse a string using the Reverse method of StringBuffer.
public class StringBufferReverse {
public static void main(String[] args) {
String blogName = "Black says Java.";
StringBuffer sb = new StringBuffer(blogName);
System.out.println("Reverse of Hei says Java is:"+ sb.reverse()); }}Copy the codeWrite a Java program that checks two strings for heterotopic words?
Explanation: An allotopic is a word that has the same letters but not in the same order, e.g. Angel and Angle.
There are several ways to solve this problem:
- Use the String method
- The Arrays. The sort ()
- Using count arrays
- Use Guava’s Multiset
Use the String class method
Ideas:
- Create a method that accepts two string variables to determine if they are allotopic words.
- Iterate over the first String word and get char C from it using the charAt() method;
- If the value of indexOf(c) for the second String word is -1, then the two strings are not anagrams;
- If the indexOf(c) of the second String word does not equal -1, the character c is removed from the second word;
- If the second String word ends with an empty String, then both words are allotopic.
public class StringAnagramMain {
public static void main(String[] args) {
String word = "Black says Java.";
String anagram = "Black says 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; }}returnanagram.isEmpty(); }}Copy the codeThe Arrays. The sort ()
Sort two strings. If the two strings are equal, then the two strings are allotopic.
public class AnagramUsingSort {
public static void main(String[] args) {
String word = "Black says Java.";
String anagram = "Black says 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);
returnString.valueOf(wordArr); }}Copy the codeUsing count arrays
Ideas:
- If two strings are of different lengths, they are not an allotopic;
- Create an array of length 256;
- Iterate over the first string str1;
- In each iteration, we increment the count of the first String str1 and decrement the count of the second String str2;
- If the count of any character is not zero at the end, the two strings are not anagrams.
The time complexity of this approach is O(n), but it requires an additional space count array.
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; }}Copy the codeUse Guava’s Multiset
If you prefer using the Guava library, you can use MultiSet to check if two strings are heterotopic.
MultiSet allows each element to appear more than once and keeps a count of each element.
Of course, this approach requires adding Guava dependencies to pom.xml.
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>27.1 the jre</version>
</dependency>
Copy the codeThe code is as follows:
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));
}
returnms1.equals(ms2); }}Copy the codeDo all characters in a string appear only once?
For example, the character P in the Apple word appears many times, so it does not conform to; All the words in “world” appear only once, so it fits.
There are several solutions to this problem:
- Use HashSet
- Use indexOf and lastIndexOf methods
- Use the ASCII value of the character
Use HashSet
Depending on the add() method of the HashSet, it returns false if an element already exists.
Steps:
- Iterate over each character, adding to the HashSet;
- If the add method of a HashSet returns false, it is not all unique characters.
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; }}Copy the codeUse indexOf and lastIndexOf methods
If indexOf and lastIndexOf return the same value for a character, there will be no repetition in that string.
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; }}Copy the codeUse the ASCII value of the character
This method is the most efficient.
Ideas:
- Create a Boolean array of length 26;
- Converts char to uppercase and gets its ASCII value;
- Subtract the ASCII value from 64 to get an index between 0 and 25;
- If the characters are not repeated, the Boolean array should have 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;
else
return false;
}
return true; }}Copy the codeHow do I find duplicate characters in a string?
Ideas:
- Create a HashMap, create a HashMap where string characters are inserted as keys and their counts as values;
- If the HashMap already contains char, increment its count by one; otherwise, char is put into the HashMap;
- If Char has a value greater than 1, that means it is a repeated character in the string.
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)); }}}Copy the codeFind all the substrings of the string?
For example: if the input is ABB, then the output should be a, B, B, AB, bb, ABB
Use the subString method of the String class to find all substrings.
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)); }}}}Copy the codeThis solution has time complexity O(n^3). Because we have two loops and the time complexity of the substring method of String is order n.
If you want to find all the different substrings of String, you need to use HashSet to remove duplicate strings.
Find all possible permutations of an input string?
Such as: input “AB”, the output/” AB “, the “BA”, “ABC” input and output (” ABC “, “ACB”, “America”, “BCA”, “Chinese”, “CAB”].
Ideas:
- Take the first character of a String and recursively enter the different positions of the rest of the String;
- Assuming String is ABC, take the first character “A”;
- Take B from BC and enter the rest of the string “C” recursively;
- If String length is 1, return “C”;
- Insert the extracted “B” into each position of the recursively returned string;
- So you get BC,CB, return;
- Insert the extracted character “A” into each position of the string that returns the result;
- Then [ABC,BAC,BCA] and [ACB,CAB,CBA] are obtained;
- The result is all the orders of 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); }}Copy the codesummary
That’s all for this episode. So, did you come up with any of these ideas? If you have a better way to welcome the message exchange.
If it helps you, giving me a “like” would be a big boost.
