Question 1. Character-wise Shift for String

source of the question: http://seanzhou.iteye.com/blog/2032981

 

Question 1 Character-wise Shift For String

  

  Implement an algorithm that can do character-wise shift for strings in either direction. For example, 

 

  To shift string "abcdef" to the left by 2 characters, you get "cdefab".

  To shift string "abcdef" to the right by 3 characters, you get "defabc"

  

  Performance requirement: assume the length of the string is n, the algorithm should finish in O(n) time and within O(1) space.

 

My Thoughts

  1.  Start from the first character, find its target position, put it there. For the character originally in target position of the first character, iteratively find its target positon and put it there again ... and so on.

 

  2.  We only need to record how many characters have been put in its correct position.

 

  3.  It's possible that n shares some common factor with m, so that after some iteration, you may go back to the first character. So you need to record where did you start. After you go back to starting point, you should go right one step if not all of the characters have found its correct position.

 

Implementation in Java

package q1;
/**
 * Question 1 Character-wise Shift For String
 * 
 * Implement an algorithm that can do character-wise shift for strings in either direction. For example, 
 * 
 * To shift string "abcdef" to the left by 2 characters, you get "cdefab".
 * To shift string "abcdef" to the right by 3 characters, you get "defabc"
 * 
 * Performance requirement: assume the length of the string is n, the algorithm should finish in O(n) time and within O(1) space.    
 * @author Sean
 *
 */

public class StringShift {
	
	public static void main(String[] args) {
		//m & n has no common factors
		assert "DEFGABC".equals(shift("ABCDEFG", 3, true));
		assert "EFGABCD".equals(shift("ABCDEFG", 3, false));
		
		//n is multiple of m
		assert "EFGHABCD".equals(shift("ABCDEFGH", 4, true));
		assert "EFGHABCD".equals(shift("ABCDEFGH", 4, false));
		
		//n and m shares a common factor
	    assert "GHIABCDEF".equals(shift("ABCDEFGHI", 6, true));
		assert "DEFGHIABC".equals(shift("ABCDEFGHI", 6, false));
		
	}

	private static String shift(String origin, int m, boolean left) {
		
		// input check
		if ( origin == null )  return null;
		
		int len = origin.length();
		
		if (len == 0 ) return origin;
		
		m %= len;
		
		if ( m == 0 ) return origin;
		
		
		//get the char array from the String
		char[] arr = new char[len];
		origin.getChars(0, len, arr, 0);
		
		//shift left or right?
		int direction = left ? -1 : 1;
		
		//record how many characters have been put in its correct position
		int found = 0;
		
	    //record the starting position of the character which we are looing for its target position
		int start = 0;
		
		//record the current position of the character which we are looking for its target position
		int current = 0;
		
		char c = arr[current];
		
		char temp;
		
		// do the shift from the beginning character
		while (found < len) {
			// find the target position , plus n is to avoid negative
			current = (direction * m + current + len) % len;
			
			// swap the source and target
			temp = c;
			c = arr[current];
			arr[current] = temp;
			
			++found;
			
			// check whether the iteration go back to the starting point
			if ( current == start) {
				current = start = ( start + 1) % len;
				c = arr[current];
			}
			
		}
		
		return new String(arr);
	}

}