刷算法(3)-字符串的编码与解码

271.字符串的编码与解码

设计一个算法，可以将一个字符串列表编码成为一个字符串。这个编码后的字符串是可以通过网络进行高效传送的，并且可以在接收端被解码回原来的字符串列表。

思路

猛一看题目很简单以为简单的拼接起来，中间加个分隔符就行了，但是输入字符串本身可能就是分隔符。所以必须还要加上长度信息，我们的加码方法是长度+”/“+字符串，比如对于”a”,”ab”,”abc”，我们就变成”1/a2/ab3/abc”，那么我们解码的时候就有规律可寻，先寻找”/“，然后之前的就是要取出的字符个数，从“/“后取出相应个数即可，以此类推直至没有”/“了。编码方法是这样，具体解码又以下三种思路。

解法1

用一个索引i来标记从哪一位开始搜索分隔符，搜索到之后截出来前面的长度信息，根据长度信息再截出来对应字符串。之后把i往后移，重新开始搜索分隔符。代码如下:

package com.company;

import java.util.ArrayList;
import java.util.List;

public class Codec1 {
    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String item : strs) {
            int length = item.length();
            sb.append(length).append("/").append(item);
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int pos = s.indexOf('/', i);
            int itemSize = Integer.parseInt(s.substring(i, pos));
            int start = pos + 1;
            int end = pos + itemSize + 1;
            if (end <= s.length()) {
                String item = s.substring(start, end);
                result.add(item);
            }
            i = end;
        }
        return result;
    }
}

解法2

和解法1类似，区别在于我们每次可以从原始输入s里把对应item截出来后重新赋值，之后从裁剪后的s继续遍历，直到s为空。

package com.company;

import java.util.ArrayList;
import java.util.List;

public class Codec2 {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String item : strs) {
            sb.append(item.length()).append("/").append(item);
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        while (!s.isEmpty()) {
            int pos = s.indexOf("/");
            int itemSize = Integer.parseInt(s.substring(0, pos));
            result.add(s.substring(pos + 1, pos + itemSize + 1));
            s = s.substring(pos + itemSize + 1);
        }
        return result;
    }
}

解法3

我们可以编码的时候通过Java里的换行符\n进行分割，读入时借助BufferReader逐行读取就行了。

package com.company;


import java.io.BufferedReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;

public class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String item : strs) {
            sb.append(item).append('\n');
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        BufferedReader br = new BufferedReader(new StringReader(s));
        String temp = null;
        try {
            while ((temp = br.readLine()) != null) {
                result.add(temp);
            }
        } catch (Exception e) {

        }
        return result;
    }
}

三种方法对比

解法	耗时	内存
解法1	7ms	39.3MB
解法2	15ms	39.8MB
解法3	23ms	38.7MB

以下为leetcode执行结果:

String基础操作

`indexOf`

从左往右查找第一次出现x的索引，如果不出现则返回-1。

/**
 * 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(str, 0)原型如下：

/**
 * 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);
}

fromIndex表示开始搜索的地方，是算在数的。

`lastIndexOf`

从最后面开始找第一次出现x的索引，索引位置还是从正向开始计算的。

/**
     * Returns the index within this string of the last occurrence of the
     * specified substring.  The last occurrence of the empty string ""
     * is considered to occur at the index value {@code this.length()}.
     *
     * <p>The returned index is the largest 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 last occurrence of the specified substring,
     *          or {@code -1} if there is no such occurrence.
     */
    public int lastIndexOf(String str) {
        return lastIndexOf(str, value.length);
    }

    /**
     * Returns the index within this string of the last occurrence of the
     * specified substring, searching backward starting at the specified index.
     *
     * <p>The returned index is the largest value <i>k</i> for which:
     * <blockquote><pre>
     * <i>k</i> {@code <=} 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 to start the search from.
     * @return  the index of the last occurrence of the specified substring,
     *          searching backward from the specified index,
     *          or {@code -1} if there is no such occurrence.
     */
    public int lastIndexOf(String str, int fromIndex) {
        return lastIndexOf(value, 0, value.length,
                str.value, 0, str.value.length, fromIndex);
    }

总结：indexOf和lastIndexOf里第二个位置参数是参与搜索的。

`substring`

substring(int beginIndex, int endIndex)截取的是从beginIndex开始到endIndex-1的字符串，截出来的长度为endIndex-beginIndex。

/**
     * Returns a string that is a substring of this string. The
     * substring begins at the specified {@code beginIndex} and
     * extends to the character at index {@code endIndex - 1}.
     * Thus the length of the substring is {@code endIndex-beginIndex}.
     * <p>
     * Examples:
     * <blockquote><pre>
     * "hamburger".substring(4, 8) returns "urge"
     * "smiles".substring(1, 5) returns "mile"
     * </pre></blockquote>
     *
     * @param      beginIndex   the beginning index, inclusive.
     * @param      endIndex     the ending index, exclusive.
     * @return     the specified substring.
     * @exception  IndexOutOfBoundsException  if the
     *             {@code beginIndex} is negative, or
     *             {@code endIndex} is larger than the length of
     *             this {@code String} object, or
     *             {@code beginIndex} is larger than
     *             {@code endIndex}.
     */
    public String substring(int beginIndex, int endIndex) {
        if (beginIndex < 0) {
            throw new StringIndexOutOfBoundsException(beginIndex);
        }
        if (endIndex > value.length) {
            throw new StringIndexOutOfBoundsException(endIndex);
        }
        int subLen = endIndex - beginIndex;
        if (subLen < 0) {
            throw new StringIndexOutOfBoundsException(subLen);
        }
        return ((beginIndex == 0) && (endIndex == value.length)) ? this
                : new String(value, beginIndex, subLen);
    }

yangq's blog