一起学数据结构和算法（三）| 字符串（线性结构）

字符串（String）

字符串是由字符组成的有限序列，在计算机中通常以字符数组形式存储，支持拼接、查找、替换等操作。

---

简介

字符串是计算机科学中最常用的数据类型之一，由一系列字符组成的有限序列。在大多数编程语言中，字符串被作为基本数据类型或者对象提供，用于表示文本。从本质上讲，字符串可以看作是一个数组，但与普通数组不同，字符串有特殊的属性和操作方法，更适合处理文本数据。在 Java 等现代编程语言中，字符串是不可变的对象，一旦创建，其内容不可被修改。

核心特性

1. 不可变性：在 Java 中，字符串一旦创建，其值不可被修改
2. 字符序列：由多个字符按顺序排列组成
3. 索引访问：可以通过索引访问单个字符，索引从0开始
4. 字符串池：Java 中常量字符串会被存储在字符串中以节省内存
5. Unicode支持：可以包含任何 Unicode 字符，支持多语言文本

基本操作

// 创建字符串
String greeting = "你好，世界！";
String name = new String("Java编程");// 字符串长度
int length = greeting.length();  // 6// 连接字符串
String message = greeting + " 欢迎学习" + name;
String sameMassage = greeting.concat(" 欢迎学习").concat(name);// 访问字符
char firstChar = greeting.charAt(0);  // '你'// 获取子字符串
String subStr = greeting.substring(0, 2);  // "你好"// 字符串比较
boolean isEqual = greeting.equals("你好，世界！");  // true
boolean ignoreCase = "Java".equalsIgnoreCase("java");  // true// 查找
int index = message.indexOf("欢迎");  // 返回"欢迎"在字符串中首次出现的索引
boolean contains = message.contains("Java");  // true// 替换
String newStr = greeting.replace('你', '我');  // "我好，世界！"// 分割
String[] parts = "苹果,香蕉,橙子".split(",");  // ["苹果", "香蕉", "橙子"]// 转换大小写（仅适用于拉丁字母）
String upper = "hello".toUpperCase();  // "HELLO"
String lower = "HELLO".toLowerCase();  // "hello"// 去除首尾空白
String trimmed = "  hello  ".trim();  // "hello"

优缺点

优点

• 易用性：提供了丰富的 API 和操作方法，处理文本更方便
• 国际化支持：支持 Unicode 字符集，可以处理各种语言的文本
• 内存优化：字符串池机制减少内存使用

应用场景

• 文本处理：处理用户输入，配置文件、日志等
• 数据解析：解析 JSON、XML、CSV等格式的数据
• 自然语言处理：文本分析、情感分析、机器翻译等
• 网络通信：http 请求参数、URL处理、网络协议等
• 用户界面：文本显示、多语言支持等

扩展

StringBuilder、StringBuffer、String

• String：不可变，适合作为常量使用
• StringBuilder：可变，非线程安全，适合单线程下频繁修改字符串
• StringBuffer：可变，线程安全，适合在多线程环境使用，但性能略低于 StringBuilder

热门题目

• 14. 最长公共前缀
• 20. 有效的括号
• 415. 字符串相加

20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例：

输入：s = “()”

输出：true

题解：

栈，后进先出（LIFO）

1. 初始化一个空栈 stack
2. 定义一个字典 mapping，用于记录右括号与左括号的对应关系
3. 遍历字符串中的每一个字符：
   1. 如果是左括号，压入栈
   2. 如果是右括号：
      1. 如果栈为空，说明没有对应的左括号，返回 False
      2. 否则，弹出栈顶元素，比较是否是对应的左括号，不是则返回 False
4. 遍历结束后，检查栈是否为空。如果栈为空，说明括号完全匹配，返回 True；反之说明有未匹配的左括号，返回 False

class Solution {public boolean isValid(String s) {// 使用 Deque 接口实现栈结构，效率优于 Stack 类Deque<Character> stack = new ArrayDeque<>();// 定义一个哈希表，用于存储右括号到左括号的映射Map<Character, Character> mapping = new HashMap<>();mapping.put(')', '(');mapping.put('}', '{');mapping.put(']', '[');// 遍历字符串中的每一个字符for (char c : s.toCharArray()) {// 如果当前字符是右括号if (mapping.containsKey(c)) {// 如果栈为空，说明没有对应的左括号，直接返回 falseif (stack.isEmpty()) {return false;}// 弹出栈顶元素，并与当前右括号对应的左括号比较char top = stack.pop();if (mapping.get(c) != top) {return false;}} else {// 如果是左括号，直接压入栈中stack.push(c);}}// 遍历结束，如果栈为空，说明所有括号都正确匹配return stack.isEmpty();}
}

参考资料

[1] Hello 算法
[2] 算法导航