sky
BAN USER/*
* find the next higher number with the same digits
*/
public static int findNextHigerNum(int num){
int[] arr = num2arr(num);
if(arr.length<=1) return num;
if(num<0) return -1 * findNextLower(arr);
return findNextHiger(arr);
}
private static int[] num2arr(int num){
if(num<0) num *= -1;
int count = 0;
int temp = num;
while(temp>0){
temp /= 10;
count++;
}
//use an array to store the num digit by digit
int[] arr = new int[count];
for(int i=0; i<count; i++){
arr[i] = num%10;
num /= 10;
}
return arr;
}
private static int findNextHiger(int[] arr){
int i = 0, j = 0;
while(arr[i]<=arr[i+1]&&i<arr.length-1){
i++;
if(i==arr.length-1) return arr2num(arr);//meaning this number is the largest possible
}
int value = arr[i+1];
while(arr[j]<=value) j++;
swap(arr, i+1, j);
//now place the the remaining part in descending order, this just need a reverse operation
reverse(arr, 0, i);
return arr2num(arr);
}
private static int findNextLower(int[] arr){
int i = 0, j = 0;
while(arr[i]>=arr[i+1]&&i<arr.length-1){
i++;
if(i==arr.length-1) return arr2num(arr);
}
int value = arr[i+1];
while(arr[j]>=value) j++;
swap(arr, i+1, j);
reverse(arr, 0, i);
return arr2num(arr);
}
private static int arr2num(int[] arr){
int poly = 1;
int value = 0;
for(int i=0; i<arr.length; i++){
value += arr[i] * poly;
poly *= 10;
}
return value;
}
private static void reverse(int[] arr, int start, int end){
while(start<end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
Assume string a with smaller size and string b with larger size
- sky April 17, 2014Logic:
1. find all anagrams of a
2. check if each anagram is a substring of b
3. return true if find one, otherwise return false.
Code:
/*
* find if a string a and all its anagram is a substring of another string b
*/
public static boolean isAnagramsSubstring(String small, String large){
if(small==null||large==null) return false;
if(small.length()>large.length()) return false;
ArrayList<String> anagrams = findAnagrams(small);
for(String s: anagrams){
if(isSubstring(s, large)) return true;
}
return false;
}
private static boolean isSubstring(String a, String b){
for(int i=0; i<b.length(); i++){
if(b.charAt(i)==a.charAt(0)){
if(b.length()-i<a.length()) return false;
String part = b.substring(i, i+a.length());
if(part.equals(a)) return true;
}
}
return false;
}
private static ArrayList<String> findAnagrams(String str){
if(str==null) return null;
return findAnagrams(str, str.length()-1);
}
private static ArrayList<String> findAnagrams(String str, int curIndex){
ArrayList<String> result = new ArrayList<String>();
if(curIndex<0){
result.add("");
return result;
}
ArrayList<String> before = findAnagrams(str, curIndex-1);
for(String s : before){
for(int i=0; i<=s.length(); i++){
String newstr = insert(s, str.charAt(curIndex), i);
result.add(newstr);
}
}
return result;
}
private static String insert(String str, char c, int pos){
String left = str.substring(0,pos);
String right = str.substring(pos);
return left + c + right;
}