首页 > 其他 > 详细

LintCode 29---交叉字符串

时间:2019-05-06 01:25:27      阅读:57      评论:0      收藏:0      [点我收藏+]

标签:||   class   bsp   lint   avi   col   mat   orm   tco   

public class Solution {
    /**
     * @param s1: A string
     * @param s2: A string
     * @param s3: A string
     * @return: Determine whether s3 is formed by interleaving of s1 and s2
     */
   public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length() + s2.length() != s3.length())
           return false;
        boolean[][] matched= new boolean[s1.length()+1][s2.length()+1];
        matched[0][0]= true;
        for(int i=1;i<= s1.length(); i++){
            if(s3.charAt(i-1) == s1.charAt(i-1))
                matched[i][0] = true;
        }
        for(int j= 1;j<= s2.length();j++){
            if(s3.charAt(j-1) == s2.charAt(j-1))
                matched[0][j] = true;
        }
        for(int i=1;i<=s1.length(); i++){
            char c1 = s1.charAt(i-1);
            for(int j = 1;j<= s2.length();j++){
                int i3 = i+ j;
                char c2 = s2.charAt(j- 1);
                char c3 = s3.charAt(i3 -1);
                if(c1 == c3)
                    matched[i][j] =matched[i][j] || matched[i-1][j];
                if( c2== c3)
                    matched[i][j] = matched[i][j] || matched[i][j-1];
            }
        }
        return matched[s1.length()][s2.length()];
    }
}

 

LintCode 29---交叉字符串

标签:||   class   bsp   lint   avi   col   mat   orm   tco   

原文:https://www.cnblogs.com/cnmoti/p/10817129.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号