📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: nibuxing
跳转到指定楼层
上一主题 下一主题
收起左侧

Zenefits电面

🔗
Quinny 2015-10-8 05:00:20 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
kennethinsnow 2015-10-20 10:53:13 | 只看该作者
全局:
我的码,对s2按2个一组处理,如果和s1当前末尾相等,就
dp[i + 1][j + 1] = dp[i - (2/4) + 1][j] + dp[i][j + 1];
否则就是 dp[i][j + 1]
可以处理各种情况s2里面同一字符跟+-都可以,s1里面有aa,aaaa,aaaaaaaa也没关系.
  1. public class Solution {
  2.         public int findMatches(String s1, String s2){
  3.        int len1 = s1.length(), len2 = s2.length();
  4.        if (len2 > len1) return 0;
  5.        if (len2 == 0 || len2 %2 != 0) return 0;
  6.        // DP matches each pattern
  7.        // number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2)
  8.        int[][] dp = new int[len1 + 1][len2 / 2 + 1];
  9.        // no match for dp[0][j]
  10.        for (int i = 1; i < len1; i++){
  11.            dp[i + 1][0] = 1;
  12.            for (int j = 0; j < len2 / 2; j++){
  13.                dp[i + 1][j + 1] = dp[i][j + 1];
  14.                if (isMatch(s1, s2, i, j)){
  15.                    if (s2.charAt(2*j + 1) == '+')
  16.                        dp[i + 1][j + 1] += dp[i - 1][j];
  17.                    else
  18.                        dp[i + 1][j + 1] += dp[i - 3][j];
  19.                }
  20.            }
  21.        }
  22.        return dp[len1][len2 / 2];
  23.    }

  24.    boolean isMatch(String s1, String s2, int i, int j){
  25.        char c = s2.charAt(j * 2);
  26.        char p = s2.charAt(j * 2 + 1);
  27.        int len = p == '+' ? 2 : 4;
  28.        if (i - len < -1) return false;
  29.        for (int h = i - len + 1; h <= i; h++){
  30.            if (s1.charAt(h) != c) return false;
  31.        }
  32.        return true;
  33.    }
  34.    
  35.    public static void main(String[] args){
  36.            Solution sln = new Solution();
  37.            // 4
  38.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-"));
  39.            // 5
  40.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-"));
  41.    }
  42. }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表