My code using DP with only one array.


  • 0
    T
    The time complexity is O(n*n),no any associative containers hah.
    
    public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] lol = new int[n];
        lol[0] = 1;
        int temp = 0;
        int start = 0;
        int j = 0;
        a:
        for (int i = 1; i <= n - 1; i++){
            if (lol[i - 1] >= 95) return lol[i - 1];
            temp = 0;
            for (j = start; j <= i - 1; j++){
                if (s.charAt(j) != s.charAt(i)){
                    temp++;
                    continue;
                }
                if (s.charAt(j) == s.charAt(i)){
                	lol[i] = (i - j) > lol[i - 1] ? (i - j) : lol[i - 1];
                	start = j + 1;
                	continue a;
                }
            }
            temp++;
            lol[i] = (temp > lol[i - 1]) ? temp : lol[i - 1];
        }
        return lol[n - 1];
    }
    

    }


  • 0
    S

    Thanks for your post. However it would be better to share solution with elaborating thoughts. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


Log in to reply
 

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