题解 | #最长公共子串#

package com.hhdd.dp;

import com.hhdd.最长公共前缀;

/**
 * 给定两个字符串str1和str2,输出两个字符串的最长公共子串
 * 题目保证str1和str2的最长公共子串存在且唯一。
 * <p>
 * 数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000
 * 要求： 空间复杂度 O(n^2)O(n
 * 2
 * )，时间复杂度 O(n^2)O(n
 * 2
 * )
 * 输入：
 * "1AB2345CD","12345EF"
 * 复制
 * 返回值：
 * "2345"
 *
 * @Author HuangLusong
 * @Date 2022/4/1 21:46
 */
public class 最长公共子串 {
    /**
     * longest common substring
     * <p>
     * <p>
     * 先暴力做吧
     *
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS(String str1, String str2) {
        // write code here
        if (str1.length() == 0 || str2.length() == 0) {
            return null;
        }
        String longer = "";
        String shorter = "";
        if (str1.length() > str2.length()) {
            longer = str1;
            shorter = str2;
        } else {
            longer = str2;
            shorter = str1;
        }
        String res = "";
        //遍历shorter
        for (int i = 0; i < shorter.length(); i++) {
            for (int j = i + 1; j <= shorter.length(); j++) {
                String temp = shorter.substring(i, j);
                if (longer.indexOf(temp) != -1) {
                    if (temp.length() > res.length()) {
                        res = temp;
                    }
                } else {
                    break;
                }
            }
        }
        return res;
    }

    /**
     * 从线到面的思考
     *
     * @param str1
     * @param str2
     * @return
     */
    public String LCS2(String str1, String str2) {
        // write code here
        if (str1.length() == 0 || str2.length() == 0) {
            return null;
        }
        int[][] flags = new int[str1.length()][str2.length()];

        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                // 遍历如果对应位置的字符串相等则将标志1存入flags
                if (str1.charAt(i) == str2.charAt(j)) {
                    flags[i][j] = 1;
                }
            }
        }
        // 直接遍历flags
        // 很容易知道所谓的子串其实就是斜线，找出最长的斜线即可
        /**
         * 如果最终resRow还是-1则说明根本没找到
         */
        int resRow = -1;
        int resLength = 0;
        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                if (flags[i][j] == 1) {
                    int tempLength = 0;
                    int tempI = i;
                    int tempJ = j;
                    while (tempI < str1.length() && tempJ < str2.length()) {
                        if (flags[tempI][tempJ] == 1) {
                            tempLength++;
                        } else {
                            break;
                        }
                        tempI++;
                        tempJ++;
                    }
                    if (tempLength > resLength) {
                        resLength = tempLength;
                        resRow = i;
                    }
                }
            }
        }
        if (resLength == 0) {
            return "";
        }
        return str1.substring(resRow, resRow + resLength);
    }

    /**
     * 通过dp找规律的方式解决，比较难想
     * dp[i][j] 表示str1和str2分别以最后i，j位置为结束的最大公共子串长度
     * 很显然i，j位置的字符必须相等
     * 递推公式dp[i][j]=dp[i-1][j-1]+1
     *
     * @param str1
     * @param str2
     * @return
     */
    public String LCS3(String str1, String str2) {
        if (str1.length() == 0 || str2.length() == 0) {
            return null;
        }
        int[][] dp = new int[str1.length()][str2.length()];
        //设置几个变量存值
        int resRow = -1;
        int resLength = 0;
        //把边界位置初始化得了，简单点
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) == str2.charAt(0)) {
                dp[i][0] = 1;
                if (dp[i][0] > resLength) {
                    resLength = dp[i][0];
                    resRow = i;
                }
            }
        }
        for (int i = 0; i < str2.length(); i++) {
            if (str2.charAt(i) == str1.charAt(0)) {
                dp[0][i] = 1;
                if (dp[0][i] > resLength) {
                    resLength = dp[0][i];
                    resRow = 0;
                }
            }
        }

        for (int i = 1; i < str1.length(); i++) {
            for (int j = 1; j < str2.length(); j++) {
                if (str1.charAt(i) != str2.charAt(j)) {
                    // 本身就是0......
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > resLength) {
                        resLength = dp[i][j];
                        resRow = i;
                    }
                }
            }
        }
        return str1.substring(resRow + 1 - resLength, resRow + 1);

    }


    public static void main(String[] args) {
        最长公共子串 demo = new 最长公共子串();
        String res = demo.LCS3("abcdefg", "ab1cdefgabc1defg");
        System.out.println("res = " + res);
    }

}