Skip to content

Instantly share code, notes, and snippets.

@adohe-zz
Created February 17, 2014 06:17
Show Gist options
  • Save adohe-zz/9045605 to your computer and use it in GitHub Desktop.
Save adohe-zz/9045605 to your computer and use it in GitHub Desktop.
left shift string implementations in Java
//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