Substring with Concatenation of All Words

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).

这道题目很容易想到如何使用brute-force解决:随着 S 字符串逐个判断是否包含于 L 里。 由于 L 中的string 可以被重复出现,例如 [“foo”, “bar” , “foo”], 在这种情况下,必须在 S 中让 “foo” 字符串出现两次, 我使用的是 HashMap<String, Integer> 来保证相同字符的出现次数不会有问题。在每次做验证前,复制map带入保证有效性。

考虑的枝剪 : 由于必须包含所有字符, 因此index 必然会是小于 (S.length – count * word.length).

下面是我的java 代码,下回会根据网上的优化代码进行修改:

public List<Integer> findSubstring(String S, String[] L) {

        List<Integer> list = new ArrayList<Integer>();

        //if it's 0 length
        if(L.length == 0)
            return list;

        int len = L[0].length();

        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(int i = 0; i < L.length; i ++){

            if(map.get(L[i]) == null)
                map.put(L[i],1);
            else
                map.put(L[i],map.get(L[i]) + 1);

        }

        for(int i = 0; i < S.length() - L.length*len + 1; i ++){

            HashMap<String,Integer> copyMap = new HashMap<String, Integer>(map);
            if(matchStr(copyMap, S.substring(i),len))
                list.add(i);

        }

        return list;
    }

    private boolean matchStr(HashMap<String,Integer> map, String s, int len){

        int start = 0;

        while(!map.isEmpty()){

            String temp = s.substring(start, start + len);

            if(map.get(temp) != null){

                int count = map.get(temp);
                count --;
                if(count == 0)
                    map.remove(temp);
                else
                    map.put(temp, count);

                start += len;
                continue;
            }else
                return false;

        }

        return true;

    }

第一篇算法训练, 希望以后能够越写越专业详细。 每天都要加油!

Advertisements
This entry was posted in 算法题 and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s