首页 > 其他 > 详细

Substring with Concatenation of All Words

时间:2014-02-18 08:08:25      阅读:282      评论:0      收藏:0      [点我收藏+]

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S"barfoothefoobarman"
L["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

 

从左往右扫描主字符串,用两个map<String, Integer>来统计字符串的出现次数. 这里L数组中可能会出现两个相同的字符串. 

 

bubuko.com,布布扣
public static ArrayList<Integer> findSubstring3(String S, String[] L) {
        ArrayList<Integer> results = new ArrayList<Integer>();
        int len = L.length;
        if (len == 0) {
            results.add(0);
            return results;
        }

        int M = S.length();
        int N = L[0].length();
        Map<String, Integer> expected = new HashMap<String, Integer>();
        Map<String, Integer> real = new HashMap<String, Integer>();
        for (int j = 0; j < len; j++) {
            if (expected.get(L[j]) == null) {
                expected.put(L[j], 1);
                real.put(L[j], 0);
            } else {
                expected.put(L[j], expected.get(L[j]) + 1);
            }
        }
        // i的遍历范围是S的长度,减去L中所有String的长度和
        for (int i = 0; i <= (M - N * len); i++) {
            int j = 0;
            for (; j < len;) {
               // 这里的j*N,j表示已经遇到的String的个数,N是L中每个String的长度 
                String tmp = S.substring(i + j * N, i + (j + 1) * N);
                if (expected.get(tmp) == null) {
                    break;
                } else {
                    real.put(tmp, real.get(tmp) + 1);
                    // 下面的if 表示如果遇到String超过 expected了 就跳出
                    if (real.get(tmp) > expected.get(tmp)) {
                        break;
                    }
                    j = j + 1;
                }
            }
            // j 表示在S中遇到L中String的个数,j == len 表示全部都遇到了
            if (j == len) {
                results.add(i);
            }

            // 这里是将real清零 重新计算遇到的在L中的String
            for (int m = 0; m < len; m++) {
                real.put(L[m], 0);
            }

        }
        return results;
    }                    
bubuko.com,布布扣

Substring with Concatenation of All Words

原文:http://www.cnblogs.com/RazerLu/p/3552060.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!