-
-
Save startupjing/3f4d8a9409d230992a6b to your computer and use it in GitHub Desktop.
my solutions--cc150 1.3
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Scanner; | |
public class StrPermutation { | |
/** | |
* ask user for two strings and decide if they are permutation of each other | |
* @param args | |
*/ | |
public static void main(String[] args){ | |
Scanner input = new Scanner(System.in); | |
System.out.println("Please enter two strings on sepaerate lines(q to quit): "); | |
while(input.hasNextLine()){ | |
String s1 = input.nextLine(); | |
if(s1.equals("q")){ | |
System.out.println("quit..."); | |
System.exit(0); | |
} | |
String s2 = input.nextLine(); | |
System.out.println("Permutation of another? " + checkPermu(s1, s2)); | |
System.out.println(); | |
System.out.println("Please enter another two strings (q to quit): "); | |
} | |
} | |
/** | |
* decide if two strings are permutations of each other | |
* @param s1 | |
* @param s2 | |
* @return true if permutation of each other and false otherwise | |
*/ | |
public static boolean checkPermu(String s1, String s2){ | |
//check the length first | |
if(s1.length() != s2.length()){ | |
return false; | |
} | |
//create character counter array | |
int[] arr1 = charCount(s1); | |
int[] arr2 = charCount(s2); | |
//check if counter for character mismatches | |
for(int i=0; i<256; i++){ | |
if(arr1[i] != arr2[i]){ | |
return false; | |
} | |
} | |
return true; | |
} | |
/** | |
* create character counter array for a given string | |
* @param s | |
* @return char counter array | |
*/ | |
public static int[] charCount(String s){ | |
int[] arr = new int[256]; | |
for(int i=0; i<s.length(); i++){ | |
arr[(int) s.charAt(i)] ++; | |
} | |
return arr; | |
} | |
} |
jyuan
commented
Jun 24, 2014
- One array is enough, One count++, another count--
- Using the (1) method, there is no need to traverse whether the item is equal to 0 again after traverse the second input string (you can consider it by yourself)
and BTW, I am a little bit confused. the space complexity is O(1)?
Should it be O(n)?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment