3
\$\begingroup\$

So,basically I am working on an algorithm for circular shifting a string upto a position.There are two parameters required here.

  1. String of text to shift
  2. Number of shifts required.

For example:

Given string: "Hello"
Shifts: 3
Final: "ollHe"

Ignore the limited validation here.

import java.lang.*;
import java.util.*;

public class Shift
{
public String shifting(String s,Integer sh)
{
    Integer shifts=sh;
    String string=s;
    char[] shifted=new char[50];
    Integer pos=0;
    for(int i=string.length();i>shifts;i--)
    {
        System.out.println(""+i);
        pos++;
        shifted[pos]=string.charAt(i-1);
    }
    System.out.println("Shifting complete");
    for(int j=0;j<shifts;j++)
    {
        System.out.println(""+j);
        pos++;
        shifted[pos]=string.charAt(j);
    }
    return new String(shifted);
}   
public static void main(String[] args) {
        System.out.println("Enter the string ");
        Scanner sc=new Scanner(System.in);
        String string=sc.nextLine();
        System.out.println("So you have entered:"+string);
        System.out.println("Enter the number of shifts:");
        Integer shifts=sc.nextInt();
        System.out.println("number of shifts is:"+shifts.toString());
        System.out.println("Shifted string:"+new Shift().shifting(string,shifts));
    }   
}

` Give your views on the code here.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ assuming that the String is at most 50 characters is dangerous. \$\endgroup\$ – MrSmith42 Dec 13 '16 at 12:57
  • \$\begingroup\$ You should add an example to your question. \$\endgroup\$ – MrSmith42 Dec 13 '16 at 12:57
  • 1
    \$\begingroup\$ (The example still looks off in rev. 3: how did the o and ll swap places?) What about string.substring(shifts) + string.substring(0, shifts)? \$\endgroup\$ – greybeard Dec 13 '16 at 14:04
  • \$\begingroup\$ ("backticks" are for inline code snippets; there is a {}-button and a keyboard shortcut (<Ctrl>+k) in the edit-window to turn the selection into a code block (prefixing every line with four additional spaces if the selection doesn't already look like this (then it removes four spaces from the start of every line).)) \$\endgroup\$ – greybeard Dec 13 '16 at 21:45
  • \$\begingroup\$ @greybeard..You are right.I was using the wrong way to do it.Hello->oHell->loHel->lloHe.Can you suggest the correct way? \$\endgroup\$ – Javasamurai Dec 14 '16 at 6:29
3
\$\begingroup\$

Do you have any constraints?

  • Is your example wrong? I would expected lloHe
  • If you are concerned of modifying your method parameters make them final. Copy it to local variables and don't change the variables is kind of useless.
  • Don't use short variables names (exception: the loop counter)
  • If you use Integer instead of int, you should handle null
  • Maybe a simple static utility method would be fine here, except you have some inheritance scenario in mind.
  • Maybe you should also indicate that you are shifting left for positive numbers
  • You should take the length of you string for the char.

Assuming your example is wrong, what about:

import java.util.Objects;
import javax.annotation.Nonnull;

public final class Shift
{
    @Nonnull
    public static String left( @Nonnull final String string, final int shift )
    {
        final int length = string.length();
        if( length == 0 ) return "";
        final int offset = ((shift % length) + length) % length; // get a positive offset

        return string.substring( offset, length ) + string.substring( 0, offset );
    }

    public static void main( String... args )
    {
        assertEquals( "loHel", Shift.left( "Hello", -2 ) );
        assertEquals( "oHell", Shift.left( "Hello", -1 ) );
        assertEquals( "Hello", Shift.left( "Hello", 0 ) );
        assertEquals( "elloH", Shift.left( "Hello", 1 ) );
        assertEquals( "lloHe", Shift.left( "Hello", 2 ) );
        assertEquals( "loHel", Shift.left( "Hello", 3 ) );
        assertEquals( "oHell", Shift.left( "Hello", 4 ) );
        assertEquals( "Hello", Shift.left( "Hello", 5 ) );
        assertEquals( "elloH", Shift.left( "Hello", 6 ) );
        assertEquals( "", Shift.left( "", 3 ) );
    }

    private static void assertEquals( String expected, String actual )
    {
        if( !Objects.equals( expected, actual ) ) throw new AssertionError( "Expected: >" + expected + "< was: >" + actual + "<" );
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Needs to take shift modulo string.length(), but otherwise this is the obvious way to do it. \$\endgroup\$ – Peter Taylor Dec 13 '16 at 15:00
  • \$\begingroup\$ @PeterTaylor It's not that simple. I completed the validation and added some tests. Keep in mind that %in java is the remainder and may become negative. \$\endgroup\$ – mheinzerling Dec 14 '16 at 5:54
  • \$\begingroup\$ Yes, that's the reason I used the word "modulo" rather than the symbol %. \$\endgroup\$ – Peter Taylor Dec 14 '16 at 8:19
0
\$\begingroup\$

("Rotation" = "shift".)

You can perform any rotation in constant time by devising a String wrapper that maintains the string itself and the index into that string which is to be considered as the head character of a rotation. Now, in order to rotate \$k\$ characters, just add \$k\$ to that internal offset and take the modulo of string length.

If you want to get a String out of that wrapper, just call its toString(). There is, however, an optimization: if the state of the wrapper is not "dirty", it returns the previous cached rotation. Otherwise, a new string will be created and the state marked as not dirty.

I had this in mind:

import java.util.Objects;

public class StringRotation {

    private final String string;
    private int headIndex;
    private boolean dirty;
    private String lastCreatedString;

    public StringRotation(String string) {
        this.string = Objects.requireNonNull(string,
                                             "The input string is null.");
        this.dirty = true;
    }

    public StringRotation rotate(int rotationCount) {
        headIndex = mod(headIndex + rotationCount, string.length());
        dirty = true;
        return this;
    }

    public char charAt(int index) {
        checkIndexWithinBounds(index);
        return string.charAt(mod(headIndex + index, string.length()));
    }

    @Override
    public String toString() {
        if (!dirty) {
            return lastCreatedString;
        }

        int stringLength = string.length();
        StringBuilder sb = new StringBuilder(stringLength);

        for (int i = 0; i < stringLength; ++i) {
            sb.append(charAt(i));
        }

        dirty = false;
        lastCreatedString = sb.toString();
        return lastCreatedString;
    }

    private void checkIndexWithinBounds(int index) {
        int stringLength = string.length();

        if (index < 0) {
            throw new IndexOutOfBoundsException(
                    "The character index is negative: " + index);
        }

        if (index >= stringLength) {
            throw new IndexOutOfBoundsException(
                    "The character index is too large: " + index + 
                    ". The length of this string is " + stringLength);
        }
    }

    private static int mod(int a, int q) {
        int ret = a % q;
        return ret < 0 ? ret + q :  ret;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; ++i) {
            System.out.println(new StringRotation("hello").rotate(i));
        }

        System.out.println("---");

        for (int i = 0; i > -10; --i) {
            System.out.println(new StringRotation("hello").rotate(i));
        }
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ Maybe a little over-engineered without further requirements :) \$\endgroup\$ – mheinzerling Dec 13 '16 at 13:14
  • 1
    \$\begingroup\$ (Pity you can't extends java.lang.String.) \$\endgroup\$ – greybeard Dec 13 '16 at 13:59
  • \$\begingroup\$ @greybeard, but it is possible to implement CharSequence, and a wrapper approach should consider it. \$\endgroup\$ – Peter Taylor Dec 13 '16 at 14:59
  • \$\begingroup\$ @PeterTaylor Perhaps. Yet CharSequence does not provide rotation methods, so using them would require StringRotation after all. \$\endgroup\$ – coderodde Dec 13 '16 at 15:04
  • \$\begingroup\$ Maybe I didn't express myself clearly enough. I was suggesting that a production version of StringRotation should implement CharSequence. (To be honest, if I went down the wrapper route then I would make the wrapper immutable with constructor StringRotation(CharSequence, int)). \$\endgroup\$ – Peter Taylor Dec 13 '16 at 15:41
0
\$\begingroup\$

In my opinion this is way better by a landslide:

import java.util.Scanner;

public class Example {

    static String shifter(String stringToShift, int numberOfShifts){
        for(int i = 0; i < numberOfShifts;i++)
        {
            // Store the character you want to shift
            char temporaryChar = stringToShift.charAt(stringToShift.length() - 1);

            // Store the character with the original String. Character first
            stringToShift = temporaryChar + stringToShift;

            // Now that we did that, the string is 1 character longer so we need to take a substring of it
            stringToShift = stringToShift.substring(0, stringToShift.length()-1);
        }

        // After everything is done return the String
        return stringToShift;
    }

    public static void main(String[] args) {
        // Start getting input
        Scanner input = new Scanner(System.in);

        // Get String input
        System.out.println("Enter the string ");
        String answer = input.nextLine();
        System.out.println("So you have entered: " + answer);

        // Get int input
        System.out.println("Enter the number of shifts:");
        int numberOfShifts = input.nextInt();
        System.out.println("number of shifts is: " + numberOfShifts);

        // Shift and print out the answer
        System.out.println("Shifted string: " + shifter(answer, numberOfShifts));

        // Close input after you're done
        input.close();

    } 

}

Pay attention at my style of coding and naming, it's better to have longer names so later you at least understand why the variable is there in the first place.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ This takes time Omega(mn) where m is the displacement of the shift and n is the length of the string. It's possible to do it in O(n). \$\endgroup\$ – Peter Taylor Dec 13 '16 at 15:03
  • \$\begingroup\$ I just wrote how to write better, more understandable code rather than efficient \$\endgroup\$ – Erlandas Aksomaitis Dec 13 '16 at 15:18
  • \$\begingroup\$ I disagree that it's better to replace a linear algorithm with a quadratic one unless you're massively reducing the constant factor. I'm not really convinced that this code is more understandable either. I can't understand the indexing in char temporaryChar = stringToShift.charAt(stringToShift.length()- i - 1);: it looks buggy and a quick test seems to support that. \$\endgroup\$ – Peter Taylor Dec 13 '16 at 15:50
  • \$\begingroup\$ oh sorry didn't notice that, i'll fix that quick \$\endgroup\$ – Erlandas Aksomaitis Dec 13 '16 at 18:33
  • \$\begingroup\$ I have to agree with @PeterTaylor. When you start writing you own code instead of using the libraries, you should get faster and not slower, especial if it get harder to read your code in the end. \$\endgroup\$ – mheinzerling Dec 14 '16 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.