V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
83f420984
V2EX  ›  程序员

请问在一个字符串中找一个不重覆且最长或者最短的的字符串的最好方法是什么( JavaScript)?

  •  
  •   83f420984 · 2017-06-23 10:13:28 +08:00 · 2774 次点击
    这是一个创建于 2693 天前的主题,其中的信息可能已经有所发展或是发生改变。
    在 LeetCode 上做字符处理的题目时,一般我用两个 for 套在一起循环遍历,最后要么超时,要么时间太长了,一直没找到特别好的方法,请问在处理这一类问题时有什么特别好的解法吗?

    比如下面的题目:

    https://leetcode.com/problems/longest-substring-without-repeating-characters

    https://leetcode.com/problems/longest-palindromic-substring/#/description
    12 条回复    2017-06-23 21:03:35 +08:00
    Arrowing
        2
    Arrowing  
       2017-06-23 13:22:21 +08:00
    982 / 983 test cases passed.
    最后一个超时了,T_T。。。
    Chrisplus
        3
    Chrisplus  
       2017-06-23 13:24:38 +08:00
    双向队列,O(N)的时间复杂度?
    wayne712
        4
    wayne712  
       2017-06-23 13:48:50 +08:00   ❤️ 1
    Longest Palindromic Substring 一点思路,
    利用两个下标,如 i, j
    假设输入"babad",
    i 不断向左边走,j 不断向右边走, 即两个下标 i 递减,j 递增
    在这过程中判断两个下标所在字符是否相等, 相等则继续下一对下标的比较,
    否则就中断循环,通过 substring,得到 i 和 j 之间的字符串。

    最坏的时间复杂度是 O(n^2)
    文字不太会表达,希望有帮助
    Magic347
        5
    Magic347  
       2017-06-23 14:52:33 +08:00   ❤️ 1
    public class Solution {
       public int lengthOfLongestSubstring(String s) {
          if (s == null || s.length() <= 0) {
       return 0;
       }
       int[] visited = new int[256];
       for (int i = 0; i < 256; i++) {
       visited[i] = -1;
       }
       int start = 0;
       int end = 0;
       int len = s.length();
       int retval = 1;
       while (end < len) {
       char ch = s.charAt(end);
       if (visited[ch] >= 0) {
       // current char is visited so far
       int currLen = end - start;
       if (currLen > retval) {
       retval = currLen;
       }
       int k = visited[ch];
       for (int i = start; i <= k; i++) {
       visited[s.charAt(i)] = -1;
       }
       start = k + 1;
       } else {
       // current char is not visited so far
       if (end == len - 1) {
       // reach the end of the string
          int currLen = end - start + 1;
          if (currLen > retval) {
          retval = currLen;
          }
          }
       }
       visited[ch] = end;
       end ++;
       }
       return retval;     
       }
    }
    Magic347
        6
    Magic347  
       2017-06-23 14:56:58 +08:00
    O(n)
    https://leetcode.com/problems/longest-substring-without-repeating-characters

    public class Solution {  
       public int lengthOfLongestSubstring(String s) {
         if (s == null || s.length() <= 0) {
           return 0;
        }
         int[] visited = new int[256];
         for (int i = 0; i < 256; i++) {
           visited[i] = -1;
        }
         int start = 0;
         int end = 0;
         int len = s.length();
         int retval = 1;
         while (end < len) {
           char ch = s.charAt(end);
           if (visited[ch] >= 0) {
            // current char is visited so far
             int currLen = end - start;
             if (currLen > retval) {
               retval = currLen;
            }
             int k = visited[ch];
             for (int i = start; i <= k; i++) {
               visited[s.charAt(i)] = -1;
            }
             start = k + 1;
          } else {
            // current char is not visited so far
             if (end == len - 1) {
              // reach the end of the string
               int currLen = end - start + 1;
               if (currLen > retval) {
                 retval = currLen;
              }
            }
          }
           visited[ch] = end;
           end ++;
        }
         return retval;
      }
    }
    YuJianrong
        7
    YuJianrong  
       2017-06-23 15:20:15 +08:00 via iPhone
    这种题目时间不是 O ( n )都肯定不对的,即使过了不过是 case 不好。
    Arrowing
        8
    Arrowing  
       2017-06-23 15:26:29 +08:00   ❤️ 1
    终于做出来了,之前思路错了。
    983 / 983 test cases passed. Status: Accepted Runtime: 155 ms
    You are here! Your runtime beats 98.17 % of javascript submissions.

    ```javascript
    /**
    * @param {string} s
    * @return {number}
    */
    var lengthOfLongestSubstring = function(s) {
    var sLen = s.length,
    maxLen = 0,
    maxStr = '',
    tmpStr,
    posIndex,
    i;

    for( i = 0 ; i < sLen; i++ ){

    tmpStr = s[i];
    posIndex = maxStr.indexOf(tmpStr);

    if(posIndex > -1){
    maxStr = maxStr.substring(posIndex + 1);
    }

    maxStr += tmpStr;
    maxLen = Math.max(maxLen, maxStr.length);
    }

    return maxLen;
    };
    ```
    momocraft
        9
    momocraft  
       2017-06-23 16:16:14 +08:00
    题目有点歧义,叫"最长不含重复子串"可能更好?"最长不重复子串"是另一个问题。
    YuJianrong
        10
    YuJianrong  
       2017-06-23 17:05:36 +08:00 via iPhone
    这样还是不行的,这是 O(m*n)复杂度,m 是 character 种类。你应该想想怎么做到 O(n)。
    提示 hashmap 的添加和查询我们一般认为是 O(1)的
    mengzhuo
        11
    mengzhuo  
       2017-06-23 18:06:28 +08:00   ❤️ 1
    就是滑动窗口嘛~~87% AC 路过

    ```
    func lengthOfLongestSubstring(s string) int {
    var dict [256]int
    for i:=0;i<256;i++{
    dict[i] = -1
    }
    start := -1
    maxLen := 0
    for i, c := range []byte(s) {
    if dict[uint8(c)] > start {
    start = dict[uint8(c)]
    }
    dict[uint8(c)] = i
    maxLen = max(i - start, maxLen)
    }
    return maxLen
    }

    func max(a,b int) int{
    if a > b {
    return a
    }
    return b
    }
    ```
    yuann72
        12
    yuann72  
       2017-06-23 21:03:35 +08:00   ❤️ 1
    983 / 983 test cases passed.
    Status: Accepted
    Runtime: 158 ms (这 Runtime 一会长的时候 190+ 短的时候 157+)
    Submitted: 0 minutes ago


    /**
    * @param {string} s
    * @return {number}
    */
    var lengthOfLongestSubstring = function(s){
    var subStrs = [],
    curSubStr = '',
    i=0,len=s.length;
    for(;i<len;i++){
    if(!curSubStr.includes(s[i])){
    curSubStr += s[i];
    }else{
    subStrs.push(curSubStr);
    curSubStr = curSubStr.slice(curSubStr.indexOf(s[i]) + 1) + s[i];
    }
    }
    subStrs.push(curSubStr);
    for(i=0,len=subStrs.length;i<len;i++){
    if (subStrs[i].length > curSubStr.length) {
    curSubStr = subStrs[i];
    }
    }
    return curSubStr.length;
    };
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5768 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 08:46 · PVG 16:46 · LAX 00:46 · JFK 03:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.