今日主题：字符串。

344. 反转字符串

问题描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

解题思路

让左指针指向第一个元素，右指针指向最后一个元素；交换两个元素的位置，然后让两个指针同时向内移动，直到两个指针相遇。

代码实现

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while(left < right){
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

17. 电话号码的字母组合

问题描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

电话按键

解题思路

看到排列问题，首先想到的就是回溯算法。
路径：前 i - 1个数字组成的字符串对应的字母组合
选择列表：第i个数字对应的字母列表
结束条件：路径长度等于给出的数字字符串的长度
做选择：从选择列表中拿出一个元素、将其加入路径

代码实现

class Solution {

    List<String> res = new ArrayList<>();
    HashMap<Character, String> choiceMap = new HashMap<>();

    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return res;
        }
        addChoices();
        LinkedList<Character> track = new LinkedList<>();
        backtrack(track, digits, 0);
        return res;
       
    }

    //回溯更新结果
    public void backtrack(LinkedList<Character> track, String digits, int index){
        if(track.size() == digits.length()){
            res.add(list2str(track));
            return;
        }

        //获取选择列表
        String choices = choiceMap.get(digits.charAt(index));
        for(int i = 0; i < choices.length(); i++){
            track.add(choices.charAt(i));
            index++;

            backtrack(track, digits, index);

            track.removeLast();
            index--;
        }
    }

    private String list2str(LinkedList<Character> track){
        StringBuilder sb = new StringBuilder();
        for(Character c : track){
            sb.append(c);
        }
        //System.out.println(sb.toString());
        return sb.toString();
    }

    private void addChoices() {
        choiceMap.put('2', "abc");
        choiceMap.put('3', "def");
        choiceMap.put('4', "ghi");
        choiceMap.put('5', "jkl");
        choiceMap.put('6', "mno");
        choiceMap.put('7', "pqrs");
        choiceMap.put('8', "tuv");
        choiceMap.put('9', "wxyz");
    }
}