Created
February 17, 2014 06:17
-
-
Save adohe-zz/9045605 to your computer and use it in GitHub Desktop.
left shift string implementations in Java
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
//One implementation that not consider the | |
//time and space complexity and use string | |
//as input | |
public final class LeftShift { | |
//brute-force algorithm | |
private String leftShiftOne(String s) { | |
if(s == null) | |
throw new NullPointerException("null"); | |
if(s.length() <= 1) | |
return s; | |
StringBuilder sb = new StringBuilder(s.subString(1, s.length())); | |
sb.append(s.charAt(0)); | |
return sb.toString(); | |
} | |
private String leftShiftM(String s, int m) { | |
while(--m >= 0) { | |
str = leftShiftOne(str); | |
} | |
return str; | |
} | |
//The third-step algorithm | |
private String reverse(String s) { | |
if(s == null) | |
throw new NullPointerException("null"); | |
if(s.length <= 1) | |
return s; | |
return new StringBuilder(s).reverse().toString(); | |
} | |
private String leftShiftN(String s, int n) { | |
return reverse(reverse(str.substring(0, n)).concat(reverse(str.substring(n, str.length())))); | |
} | |
} | |
//Another implementation that use brute-force algorithm | |
//and accept char[] as input | |
public final class LeftShiftTwo { | |
private void leftShiftOne(char[] arr) { | |
if(arr == null) | |
throw new NullPointerException("null"); | |
if(arr.length <= 1) | |
return; | |
char c = arr[0]; | |
for(int i = 1; i < arr.length; i++) { | |
arr[i - 1] = arr[i]; | |
} | |
arr[arr.length - 1] = c; | |
} | |
private void leftShiftM(char[] arr, int m) { | |
while(--m >= 0) { | |
leftShiftOne(arr); | |
} | |
} | |
} | |
//Another implementation that use three-steps algorithm | |
//and accept char[] as input | |
public final class LeftShiftThree { | |
private void reverse(char[] arr, int begin, int end) { | |
if(begin < 0 || end > arr.length || begin > end) | |
throw new IndexOutOfBoundsException(); | |
while(begin < end) { | |
char t = arr[begin]; | |
arr[begin++] = arr[end]; | |
arr[end--] = t; | |
} | |
} | |
//Actually there is a bug: if the m is bigger | |
//than the char array length, then how to do | |
//with the algorithm | |
private void leftShiftM(char[] arr, int m) { | |
if(m == null) | |
throw new NullPointerException("null"); | |
if(m.length <= 1) | |
return; | |
m %= arr.length; | |
reverse(arr, 0, m - 1); | |
reverse(arr, m, arr.length - 1); | |
reverse(arr, 0, arr.length - 1); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment