网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

【Lintcode】1456. Word Synthesis Problem

2021/6/25 2:44:51 人评论

题目地址: https://www.lintcode.com/problem/1456/description 给定一个英文小写单词sss,再给定一个字符串数组AAA。问是否能从AAA的每一个字符串中取出一个字符,使得它们可以恰好拼出单词sss。 考虑一个二分图,左边是sss的各…

题目地址:

https://www.lintcode.com/problem/1456/description

给定一个英文小写单词 s s s,再给定一个字符串数组 A A A。问是否能从 A A A的每一个字符串中取出一个字符,使得它们可以恰好拼出单词 s s s

考虑一个二分图,左边是 s s s的各个字母的下标 s [ 0 , 1 , . . . , l s − 1 ] s[0,1,...,l_s-1] s[0,1,...,ls1],右边是 0 , 1 , . . . , l A − 1 0,1,...,l_A-1 0,1,...,lA1各个数字,如果 s [ i ] s[i] s[i] A [ j ] A[j] A[j]中恰好出现,则将 i i i j j j之间连边。显然如果能拼出,则说明最大匹配数恰好是 l s l_s ls,反之也成立,所以问题转化为最大匹配是否等于 l s l_s ls,可以用匈牙利算法,参考https://blog.csdn.net/qq_46105170/article/details/113830924。代码如下:

import java.util.*;

public class Solution {
    /**
     * @param target: the target string
     * @param words:  words array
     * @return: whether the target can be matched or not
     */
    public boolean matchFunction(String target, String[] words) {
        // Write your code here
        int n = words.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] match = new int[n];
        Arrays.fill(match, -1);
        boolean[] visited = new boolean[n];
        for (int i = 0; i < target.length(); i++) {
            for (int j = 0; j < n; j++) {
                if (words[j].indexOf(target.charAt(i)) != -1) {
                    map.putIfAbsent(i, new ArrayList<>());
                    map.get(i).add(j);
                }
            }
        }
        
        int cnt = 0;
        for (int i = 0; i < target.length(); i++) {
            Arrays.fill(visited, false);
            if (dfs(i, match, visited, map)) {
                cnt++;
            }
        }
        
        return cnt == target.length();
    }
    
    private boolean dfs(int idx, int[] match, boolean[] visited, Map<Integer, List<Integer>> map) {
        if (!map.containsKey(idx)) {
            return false;
        }
    
        for (int next : map.get(idx)) {
            if (!visited[next]) {
                visited[next] = true;
                if (match[next] == -1 || dfs(match[next], match, visited, map)) {
                    match[next] = idx;
                    return true;
                }
            }
        }
        
        return false;
    }
}

时空复杂度 O ( l s l A ) O(l_sl_A) O(lslA)

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?