Skip to content

Instantly share code, notes, and snippets.

@startupjing
Created June 16, 2014 05:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save startupjing/3f4d8a9409d230992a6b to your computer and use it in GitHub Desktop.
Save startupjing/3f4d8a9409d230992a6b to your computer and use it in GitHub Desktop.
my solutions--cc150 1.3
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
Copy link

jyuan commented Jun 24, 2014

  1. One array is enough, One count++, another count--
  2. 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)

@jackson-rz
Copy link

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