Uses Longest Increasing Subsequence & Subset Enumeration (DFS)


  • 0
    C

    My solution finds the longest matching pattern of string 1 in string 2.
    So for word1 = "adbac" and word2 = "abc" , the longest matching pattern (not necessarily continuous) is "abc"
    How ? we can remove 'd' & second 'a' from "adbac" to get "abc".
    The way I find the longest matching pattern is through longest increasing subsequence . (standard dp)
    After than, the minimum can be found using simple math.

    public class Solution {
    
    List<List<Integer>> sequences = new ArrayList<List<Integer>>();
    void printer(List<Integer> seq){
        for(int i=0;i<seq.size();i++)
            System.out.print(seq.get(i) + " ");
        System.out.println();
    }
    void form(int cur,List<Integer> sequence,List<List<Integer>>array){
        if(cur == array.size()){
            List<Integer> copy = new ArrayList<Integer>();
            for(int i=0; i<sequence.size();i++)
                copy.add(sequence.get(i));
            sequences.add(copy);
            return;
        }
        List<Integer> options = array.get(cur);
        for(int i=0;i<options.size();i++){
            sequence.add(options.get(i));
            form(cur+1,sequence,array);
            sequence.remove(sequence.size()-1);
        }
    }
    
    # find longest increasing subsequence for a given sequence
    List<Integer> get_lis (List<Integer> sequence){
        List<Integer> dp = new ArrayList<Integer>();
        Map<Integer,Integer> path = new HashMap<Integer,Integer>();
        List<Integer> lis = new ArrayList<Integer>();
        dp.add(1);
        path.put(0,-1);
        int maxpos = 0;
        for(int i=1;i<sequence.size();i++){
            if(sequence.get(i) == -1){
                dp.add(-1);
                continue;
            }
            dp.add(1);
            path.put(i,-1);
            for(int j=0;j<i;j++){
                if(sequence.get(j) < sequence.get(i) && dp.get(j) >= dp.get(i)){
                    dp.set(i,dp.get(j)+1);
                    path.put(i,j);
                }
            }
            if(dp.get(i)>dp.get(maxpos))
                maxpos = i;
        }
        Set<Integer> in_lis = new HashSet<Integer>();
        int pos = maxpos;
        while(true){
            if(pos == -1)
                break;
            in_lis.add(pos);
            pos = path.get(pos);
        }
        int count = 0;
        for(int i=0;i<sequence.size();i++){
            if(in_lis.contains(i)){
                lis.add(sequence.get(i));
                count++;
            }
            else
                lis.add(-1);
        }
        lis.add(count);
        return lis;
    }
    
    public int minDistance(String word1, String word2) {
        
       # form a map from characters that appear in word2 to a list of indices they appear in
        
        HashMap<Character,List<Integer>> map = new HashMap<Character,List<Integer>>();
        for(int i=0;i<word2.length();i++){
            char c = word2.charAt(i);
            if(!map.containsKey(c)){
                ArrayList<Integer> l = new ArrayList<Integer>();
                l.add(i);
                map.put(c,l);
            }
            else{
                List<Integer> l = map.get(c);
                l.add(i);
            }
        }
        
        # form a map from each index in word1 to the possible positions of that character in word2
        List<List<Integer>> array = new ArrayList<List<Integer>>();
        for(int i=0;i<word1.length();i++){
            char c = word1.charAt(i);
            List<Integer> l;
            if(!map.containsKey(c)){
               l = new ArrayList<Integer>();
               l.add(-1);
            }
            else
                l = map.get(c);
            array.add(l);
        }
        
        
        List<Integer> sequence = new ArrayList<Integer>();      #empty sequence just for the purpose of DFS
        
        # from the above map, each index in word1 can have multiple values. For example, for word1 = "abc"
        and word2 = "aad" , the values for index 0 ('a') for word1 are 0 and 1, because  'a' appears at
        indices 0 and 1 in word2. So we form all sequences for all possible values of each index of word1.
        
        form(0,sequence,array);                 # form all possible sequences
        
        
        # the following part gets the maximum longest possible subsequence from all possible sequences
        List<Integer> final_lis = new ArrayList<Integer>();
        int maxlen=0;
        for(int i=0; i<sequences.size();i++){
            sequence = sequences.get(i);
            List<Integer> lis = get_lis(sequence);
            int lislen = lis.get(lis.size()-1);
            if(lislen>maxlen){
                maxlen = lislen;
                lis.remove(lis.size()-1);
                final_lis = lis;
            }
        }
        
        #simple math to get the final answer
        int answer = 0;
        int i=0;
        int previ=0;
        int prevval=0;
        while(i<final_lis.size()){
            if(final_lis.get(i) == -1){
                i++;
                continue;
            }
            
            int diff1 = final_lis.get(i) - prevval -1;
            int diff2 = i - previ -1;
            answer += Math.max(diff1,diff2);
            previ = i;
            prevval = final_lis.get(i);
            i++;
        }
        
        int diff1 = word1.length() - previ;
        int diff2 = word2.length() - prevval;
        answer += Math.max(diff1,diff2);
        return answer;
    }
        
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.