找出字符串中的最长连续数字子串

怼烎@ 2022-06-08 05:27 217阅读 0赞

## 题目 ##

> 给出一个字符串作为输入，找出其中最长的连续数字串并返回其长度和起始index。如果存在长度相同的连续数字串，返回最后一个连续数字串。如果没有，返回0和0。

## Analysis ##

对于这道题目，首先我们需要进一步缩小题目范围。题目中并没有给出字符串中的数字都是什么数字。比如是否包含负数，是否包含小数等。因此简单起见，我们假设该输入字符串中只包含正整数。且假设输入字符串中没有空格。

设输入字符串的长度为`n`。

从Best Conceivable Time的角度考虑，这道题的时间复杂度至少为`O(n)`。也就是说，对于这道题而言，我们至少需要遍历整个输入的字符串一次才能得出答案。因此在时间复杂度角度考虑，我们并没有多少优化的空间。

从空间复杂度的角度考虑，brute-force解法比较直观，就是遍历一遍整个输入字符串，找出并记录其中所有的连续数字子串。然后在所有被记录的数字子串中找出最长的那个。因为题目要求有多个最长子串时返回最后一个，所以我们只需要返回最后一个被记录的最长子串即可。这个方法最坏情况下需要记录整个输入字符串。所以空间复杂度为`O(n)`。

具体实现如下：

public class LongestNumberSubstring {
        public static int[] findLongestNumSubstring(String input) {
            // If the string is empty, return [0, 0] directly.
            if (input == null || input.length() == 0) {
                return new int[]{
       0, 0};
            }
    
            int index = 0;
            int[] ret = new int[]{
       0, 0}; //[start_index, length]
            while (index < input.length()) {
                StringBuilder sb = new StringBuilder();
                while (index < input.length() && Character.isDigit(input.charAt(index))) {
                    sb.append(input.charAt(index));
                    index++;
                }
    
                // If current substring is not empty and is longer than or equal to the previously found substring
                // Put it in return values.
                if (sb.length() != 0 && ret[1] <= sb.length()) {
                    ret[1] = sb.length();
                    ret[0] = index - sb.length();
                }
                index++;
            }
    
            return ret;
        }

## 优化 ##

但事实上，考虑到我们需要的只是子字符串的起始index和长度，这道题可以用2 pointers的方法解决。并不需要记录中间产生的任何子字符串。这样的话我们可以将算法的空间复杂度降到`O(1)`。

具体算法为：从头到尾遍历字符串，每当遇到数字连续数字子串时，记录其长度。并与全局记录的最长长度相比较。如果更长的话，就记录当前长度和开始index。

实现如下：

public class LongestNumberSubstring {
        
        public static int[] findLongestNumSubstring(String input) {
            // If the string is empty, return [0, 0] directly.
            if (input == null || input.length() == 0) {
                return new int[]{
       0, 0};
            }
    
            int index = 0;
            int[] ret = new int[]{
       0, 0}; //[start_index, length]
            int currLen = 0;
            while (index < input.length()) {
                currLen = 0;
                while (index < input.length() && Character.isDigit(input.charAt(index))) {
                    currLen++;
                    index++;
                }
    
                // If current substring is longer than or equal to the previously found substring
                // Put it in return values.
                if (currLen != 0 && ret[1] <= currLen) {
                    ret[1] = currLen;
                    ret[0] = index - currLen;
                }
                index++;
            }
    
            return ret;
        }
    }