2017-06-13

【字符串】判断两字符串是否互为旋转词？

字符串逆序问题的解决方法

题目：

如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。

比如A=”12345”,A的旋转词有”12345”,”23451”,”34512”,”45123”和”51234”。

对于两个字符串A和B，请判断A和B是否互为旋转词。

给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。

测试样例：

“cdab”,4,”abcd”,4

返回：true

通过代码：

import java.util.*;

public class Rotation
{
    public static boolean chkRotation(String A, int lena, String B, int lenb) {
        // write code here
        if (lena != lenb){
            return false;
        }else {
            String str = A + A;
            return str.contains(B);
        }
    }
}

也可以使用 indexOf。

其区别是：

contains 是找指定字符串是否包含一个字符串，返回值的 boolean 类型，即只有 true 和 false

indexOf 有多个重载，但无论哪个，都是做一定的匹配，然后把匹配的第一个字符的位置返回，返回的是 int 类型，如果没找到，那么返回 -1

稍微再深究一下的我看了下 contains 的源码，结果发现他调用的是 indexOf 方法。

源码如下：

/**
     * Returns true if and only if this string contains the specified
     * sequence of char values.
     *
     * @param s the sequence to search for
     * @return true if this string contains {@code s}, false otherwise
     * @since 1.5
     */
    public boolean contains(CharSequence s) {
        return indexOf(s.toString()) > -1;
    }

意思就是如上面的区别所说的，他只有两个返回值 true 和 false。

于是我们继续看一下 indexOf 方法的源码：

/**
     * Returns the index within this string of the first occurrence of the
     * specified substring.
     *
     * <p>The returned index is the smallest value <i>k</i> for which:
     * <blockquote><pre>
     * this.startsWith(str, <i>k</i>)
     * </pre></blockquote>
     * If no such value of <i>k</i> exists, then {@code -1} is returned.
     *
     * @param   str   the substring to search for.
     * @return  the index of the first occurrence of the specified substring,
     *          or {@code -1} if there is no such occurrence.

    public int indexOf(String str) {
        return indexOf(str, 0);
    }

继续可以发现他又调用了 indexOf 的两个参数方法，只不过索引是 0 。

然后我继续看带有两个参数的 indexOf 方法源码如下：

/**
     * Returns the index within this string of the first occurrence of the
     * specified substring, starting at the specified index.
     *
     * <p>The returned index is the smallest value <i>k</i> for which:
     * <blockquote><pre>
     * <i>k</i> &gt;= fromIndex {@code &&} this.startsWith(str, <i>k</i>)
     * </pre></blockquote>
     * If no such value of <i>k</i> exists, then {@code -1} is returned.
     *
     * @param   str         the substring to search for.
     * @param   fromIndex   the index from which to start the search.
     * @return  the index of the first occurrence of the specified substring,
     *          starting at the specified index,
     *          or {@code -1} if there is no such occurrence.
     */

    public int indexOf(String str, int fromIndex) {
        return indexOf(value, 0, value.length,
                str.value, 0, str.value.length, fromIndex);
    }

哈哈，发现他又调用了 indexOf 的方法，这次终于我们可以看到最后的 查找算法 如下：

/**
 * Code shared by String and StringBuffer to do searches. The
 * source is the character array being searched, and the target
 * is the string being searched for.
 *
 * @param   source       the characters being searched.
 * @param   sourceOffset offset of the source string.
 * @param   sourceCount  count of the source string.
 * @param   target       the characters being searched for.
 * @param   targetOffset offset of the target string.
 * @param   targetCount  count of the target string.
 * @param   fromIndex    the index to begin searching from.
 */
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    if (fromIndex < 0) {
        fromIndex = 0;
    }
    if (targetCount == 0) {
        return fromIndex;
    }

    char first = target[targetOffset];
    int max = sourceOffset + (sourceCount - targetCount);

    for (int i = sourceOffset + fromIndex; i <= max; i++) {
        /* Look for first character. */
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }

        /* Found first character, now look at the rest of v2 */
        if (i <= max) {
            int j = i + 1;
            int end = j + targetCount - 1;
            for (int k = targetOffset + 1; j < end && source[j]
                    == target[k]; j++, k++);

            if (j == end) {
                /* Found whole string. */
                return i - sourceOffset;
            }
        }
    }
    return -1;
}