【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串

共以下 2 个回答

• 别扒拉我 普通 2023年9月15日 上午10:22

  1、状态定义：dp[i]表示以下标i结尾的字符串最长不含重复子串的长度, 使用一个hashmap
  2、转移方程：如果map中没有当前这个元素，那么dp[i]=dp[i-1]+1
  如果map中存在当前的元素，一开始的想法是 dp[i]=i-map.get(array[i]),但是这样想有点问题，如果当前的字符串是abba的时候,按照刚才的思路dp[0]=1 dp[1]=2 dp[2]=1 dp[3]=3
  但是dp[3]是错误的，因为中间存在了重复的字符。所以要加一种情况。
  dp[i]=Math.min(dp[i-1]+1,i-map.get(s.charAt(i)))
  3、初始状态：dp[0] = 1

  class Solution {
      public int lengthOfLongestSubstring(String s) {
          if(s.isEmpty()){
              return 0;
          }
          Map<Character, Integer> mp = new HashMap<>();
          int res = 1;
          int[] dp = new int[s.length()];
          dp[0] = 1;
          mp.put(s.charAt(0), 0);
          for(int i=1; i<s.length(); i++){
              if(!mp.containsKey(s.charAt(i))){
                  dp[i] = dp[i-1] + 1;
              }else{
                  dp[i] = Math.min(dp[i-1]+1, i-mp.get(s.charAt(i)));
              }
              mp.put(s.charAt(i), i);
              res = Math.max(res, dp[i]);
          }
          return res;
       }
  }
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年9月13日 下午10:12

  思路和地哥答案类似，不过没用map来存位置，导致慢了

  class Solution {
      public int lengthOfLongestSubstring(String s) {
          if (s == null || s.length() == 0) {
              return 0;
          }
          //dp[i]表示以i字符结尾的，不含最长子字符串的长度
          int max = 1;
          int cur = 1;
          for (int i = 1; i < s.length(); i++) {
              int count = 1;
              for (int j = 1; j <= cur; j++) {
                  char target = s.charAt(i);
                  if (s.charAt(i-j) == target) {
                      cur = count;
                     break;
                  } 
                  count++;
              }
              cur = count;
              max = Math.max(max, cur);
          }
  
          return max;
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复