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

字符串（String）

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

简介

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

核心特性

不可变性：在 Java 中，字符串一旦创建，其值不可被修改
字符序列：由多个字符按顺序排列组成
索引访问：可以通过索引访问单个字符，索引从0开始
字符串池：Java 中常量字符串会被存储在字符串中以节省内存
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）

初始化一个空栈 stack
定义一个字典 mapping，用于记录右括号与左括号的对应关系
遍历字符串中的每一个字符：
1. 如果是左括号，压入栈
2. 如果是右括号：
  1. 如果栈为空，说明没有对应的左括号，返回 False
  2. 否则，弹出栈顶元素，比较是否是对应的左括号，不是则返回 False
遍历结束后，检查栈是否为空。如果栈为空，说明括号完全匹配，返回 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();}
}