【必备算法】字符串（基础问题）：LeetCode题 58. 最后一个单词的长度，14. 最长公共前缀

比眉伴天荒 2022-12-15 12:45 10阅读 0赞

## [58. 最后一个单词的长度¹][58.] ##

给定一个仅包含大小写字母和空格 `' '` 的字符串 `s`，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回 0 。

**说明**：一个单词是指仅由字母组成、不包含任何空格字符的 **最大子字符串**。

**示例:**

输入: "Hello World"
    输出: 5

### 解法：顺推 ###

*  思路：不是找出最后一个字符串后再求长度，而是直接找到最后一个单词起始索引，然后用长度减去就行
 *  复杂度：
    
     *  Time：O(n）
     *  Space：O(1)

// 关键测试用例："A" = 1, " A" = 1 ,"A " = 1
    public int lengthOfLastWord(String s) {
        
            if(s.length() == 0) return 0;
    		
        	// 寻找去掉尾部空格的长度
        	// 1.去掉首尾空格的长度
            int length = s.trim().length();
            // 2.首部空格不能去。所以，如果首部有空格，则将首部空格的长度加上
            for (int i = 0; i < s.length() ; i++) {
        
                if (s.charAt(i) != ' ') break;
                length++;
            }
    		
        	// 寻找最后一个空格位置
        	// 注：-1也保证了 “A”=1
            int lastSpaceIdx = -1;
            for (int i = 0; i <length; i++) {
        
                if (s.charAt(i) == ' ') lastSpaceIdx = i;
            }
        	// 最后单词长度 = （length - 1） - (lastSpaceIdx + 1) + 1
            return length - lastSpaceIdx - 1;
    }

## [14. 最长公共前缀¹][14.] ##

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 `""`。

**示例 1:**

输入: ["flower","flow","flight"]
    输出: "fl"

**示例 2:**

输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。

**说明:**

所有输入只包含小写字母 `a-z` 。

### 解法：顺推 ###

*  思路：依次寻找每个字符，寻找的方式是遍历所有字符串，如果相同位置存在不同字符则返回
 *  复杂度

public String longestCommonPrefix(String[] strs) {
        
            if (strs.length < 1) return "";
        	// 找最短串，因为公共最长子串的最长情况=最短串
            int minLen = Integer.MAX_VALUE;
            for (int i = 0; i < strs.length; i++) 
                minLen = Math.min(minLen, strs[i].length());
            // 挨个遍历所有字符
            for (int i = 0; i < minLen; i++) 
                // 判断所有字符串中是否相同
                for (int j = 0; j < strs.length - 1; j++) 
                	// 相同位置不同字符，返回结果
                    if (strs[j].charAt(i) != strs[j + 1].charAt(i)) 
                        return strs[j].substring(0, i); // subString[O,i)                                  
            return strs[0].substring(0, minLen);
        }

[58.]: https://leetcode-cn.com/problems/length-of-last-word/
[14.]: https://leetcode-cn.com/problems/longest-common-prefix/