Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Cyclic Words

Problem Statement

We can think of a cyclic word as a word written in a circle. To represent a cyclic word, we choose an arbitrary starting position and read the characters in clockwise order. So, "picture" and "turepic" are representations for the same cyclic word.

You are given a String[] words, each element of which is a representation of a cyclic word. Return the number of different cyclic words that are represented.

I have included my attempt below, and I'm not sure whether to be pleased with it or not (because I'm new to algos). I want to solve this problem in the most efficient way, preferably in an imperative language such as Java.

I would appreciate criticism of my code in terms of both function and form.

private static int countCyclicWords(String[] input) {
    HashSet<String> hashSet = new HashSet<String>();
    String permutation;
    int count = 0;

    for (String s : input) {
        if (hashSet.contains(s)) {
            continue;
        } else {
            count++;
            for (int i = 0; i < s.length(); i++) {
                permutation = s.substring(1) + s.substring(0, 1);
                s = permutation;
                hashSet.add(s);
            }
        }
    }

    return count;
}
share|improve this question
1  
"efficient" depends on some requirements and/or further clarification. For readability and form, this solution will work. A simple and easy understandable solution is always better as a complex solution because of optimization. Only if you have to optimize, look at the requirements, profile and start optimizing. Otherwise, just do not care. –  tb- Jan 21 '13 at 17:59
add comment

1 Answer

up vote 3 down vote accepted

There's one trick which you can use to get a reduction in memory usage which is very worthwhile if the strings are long. String.substring returns a new String object but wrapping the same underlying char[] as the original. So your code:

        for (int i = 0; i < s.length(); i++) {
            permutation = s.substring(1) + s.substring(0, 1);
            s = permutation;
            hashSet.add(s);
        }

could be replaced with

        String dbl = s + s;
        for (int i = 0; i < s.length(); i++) {
            hashSet.add(dbl.substring(i, i + s.length()));
        }

and will contain the same strings but only store 2 * s.length() characters rather than s.length() * s.length().


The next trick to consider using would be a CharSequence implementation which wraps the original string and an offset for the starting character.


Finally, you could consider normalising each cyclic word. Given the s.length() possible rotations, choose the lexicographically smallest and insert only that one into the set. Whether this gives an efficiency improvement will depend on the statistics of the strings, but if they're random and of a length comparable to the size of the alphabet then a naïve algorithm for finding the smallest will be essentially linear, and you gain two things: firstly, the set becomes smaller (less memory usage, faster lookups); and secondly, you can drop count because the number of cyclic words will be just the size of the set.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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